Total nondeterministic Turing machines and a p-optimal proof system for SAT

DOI10.1007/978-3-319-58741-7_34zbMath1489.68095OpenAlexW2613545522MaRDI QIDQ2011675

Zenon Sadowski

Publication date: 4 August 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-58741-7_34

zbMATH Keywords

disjoint NP-pairsoptimal propositional proof systemp-optimal proof system for SATtotal Turing machines

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of proofs (03F20) Classical models of computation (Turing machines, etc.) (68Q04) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Unnamed Item
• Nondeterministic functions and the existence of optimal proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Tuples of disjoint \(\mathsf{NP}\)-sets
• Optimal proof systems imply complete sets for promise classes
• Inverting onto functions.
• Do there exist complete sets for promise classes?
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems

This page was built for publication: Total nondeterministic Turing machines and a p-optimal proof system for SAT