OAI/Computability/MaxCut/Machines/RawInitialMachineBudget.lean

GitHub source file

12 declarations, 0 contain sorry, 0 declared as axioms

Polynomial arithmetic for the actual initial-machine phase counts. The separate execution theorem must connect these counts to the concrete program.

  1. def OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.nameSum line 13
  2. def OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.bodyTime line 16
  3. def OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.loopTime line 20
  4. theorem OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.nameSum_le line 24
  5. theorem OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.bodyTime_le line 31
  6. theorem OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.loopTime_le line 38
  7. theorem OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.input_header_bound line 60
  8. theorem OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.graph_size_bound line 66
  9. def OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.fullBudget line 73
  10. def OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.timePolynomial line 77
  11. theorem OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.timePolynomial_eval line 81
  12. theorem OAI.MaxCutGames.Foundations.PCP.RawInitialMachineBudget.fullBudget_le line 85