OAI/Computability/MaxCut/Encoding/Serialization.lean

GitHub source file

23 declarations, 0 contain sorry, 0 declared as axioms

Concrete finite-alphabet serialization primitives. A natural word n is n one-bits followed by a zero delimiter. These are size and decoding theorems, not running-time certificates. In particular, output length is never called runtime.

  1. def OAI.MaxCutGames.Foundations.Complexity.encodeWord line 14
  2. def OAI.MaxCutGames.Foundations.Complexity.encodeWords line 16
  3. def OAI.MaxCutGames.Foundations.Complexity.decodeWordsAux line 20
  4. def OAI.MaxCutGames.Foundations.Complexity.decodeWords line 26
  5. theorem OAI.MaxCutGames.Foundations.Complexity.decodeWordsAux_word line 28
  6. theorem OAI.MaxCutGames.Foundations.Complexity.decodeWords_encodeWords line 38
  7. theorem OAI.MaxCutGames.Foundations.Complexity.encodeWords_injective line 46
  8. theorem OAI.MaxCutGames.Foundations.Complexity.encodeWord_length line 51
  9. theorem OAI.MaxCutGames.Foundations.Complexity.encodeWords_append line 54
  10. theorem OAI.MaxCutGames.Foundations.Complexity.encodeWords_length line 60
  11. theorem OAI.MaxCutGames.Foundations.Complexity.encodeWords_length_le line 66
  12. def OAI.MaxCutGames.Foundations.Complexity.literalWords line 80
  13. def OAI.MaxCutGames.Foundations.Complexity.clauseWords line 83
  14. def OAI.MaxCutGames.Foundations.Complexity.formulaWords line 86
  15. def OAI.MaxCutGames.Foundations.Complexity.formulaBits line 89
  16. theorem OAI.MaxCutGames.Foundations.Complexity.literalWords_length line 91
  17. theorem OAI.MaxCutGames.Foundations.Complexity.clauseWords_length line 94
  18. theorem OAI.MaxCutGames.Foundations.Complexity.clausesWords_length line 97
  19. theorem OAI.MaxCutGames.Foundations.Complexity.formulaWords_length line 106
  20. theorem OAI.MaxCutGames.Foundations.Complexity.literalBits_length_le line 111
  21. theorem OAI.MaxCutGames.Foundations.Complexity.clauseBits_length_le line 116
  22. theorem OAI.MaxCutGames.Foundations.Complexity.clausesBits_length_le line 124
  23. theorem OAI.MaxCutGames.Foundations.Complexity.formulaBits_length_le line 134