Pages that link to "Item:Q1398371"

The following pages link to Optimal proof systems imply complete sets for promise classes (Q1398371):

Displaying 27 items.

• Towards NP-P via proof complexity and search (Q408544) (← links)
• Proof systems that take advice (Q553297) (← links)
• The shrinking property for NP and coNP (Q627189) (← links)
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography (Q693058) (← links)
• Nondeterministic functions and the existence of optimal proof systems (Q837177) (← links)
• Classes of representable disjoint \textsf{NP}-pairs (Q884465) (← links)
• Tuples of disjoint \(\mathsf{NP}\)-sets (Q929286) (← links)
• The deduction theorem for strong propositional proof systems (Q987382) (← links)
• Promise problems complete for complexity classes (Q1109568) (← links)
• Total nondeterministic Turing machines and a p-optimal proof system for SAT (Q2011675) (← links)
• Further oracles separating conjectures about incompleteness in the finite domain (Q2210516) (← links)
• An oracle separating conjectures about incompleteness in the finite domain (Q2290649) (← links)
• Reductions between disjoint NP-pairs (Q2387199) (← links)
• A Parameterized Halting Problem (Q2908544) (← links)
• Do there exist complete sets for promise classes? (Q3107337) (← links)
• Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes (Q3392941) (← links)
• Logical Closure Properties of Propositional Proof Systems (Q3502657) (← links)
• The Shrinking Property for NP and coNP (Q3507436) (← links)
• On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS (Q3636159) (← links)
• Does Advice Help to Prove Propositional Tautologies? (Q3637158) (← links)
• INCOMPLETENESS IN THE FINITE DOMAIN (Q4640304) (← links)
• P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle (Q5092409) (← links)
• (Q5422270) (← links)
• The Complexity of Propositional Proofs (Q5444711) (← links)
• The Deduction Theorem for Strong Propositional Proof Systems (Q5458838) (← links)
• Hard Instances of Algorithms and Proof Systems (Q5892128) (← links)