Nondeterministic instance complexity and hard-to-prove tautologies
From MaRDI portal
Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Recommendations
- Nondeterministic Instance Complexity and Proof Systems with Advice
- On the computational complexity of finding hard tautologies
- Hard instances of algorithms and proof systems
- Hard instances of algorithms and proof systems
- Complexity of t-tautologies
- Strong nondeterministic Turing reduction - a technique for proving intractability
- scientific article; zbMATH DE number 3982519
- Completeness for nondeterministic complexity classes
- Proof Complexity of Non-classical Logics
- Proof complexity of non-classical logics
Cited in
(12)- Mirror images and schemes for the maximal complexity of nondeterminism
- Nondeterministic Instance Complexity and Proof Systems with Advice
- scientific article; zbMATH DE number 1114014 (Why is no real title available?)
- Generating hard tautologies using predicate logic and the symmetric group
- Complexity in the case against accuracy: When building one function-free Horn clause is as hard as any
- On the computational complexity of finding hard tautologies
- Using Nondeterminism to Amplify Hardness
- Proof systems that take advice
- Hard instances of algorithms and proof systems
- Hard instances of algorithms and proof systems
- Nondeterministic seedless oritatami systems and hardness of testing their equivalence
- Nondeterministic functions and the existence of optimal proof systems
This page was built for publication: Nondeterministic instance complexity and hard-to-prove tautologies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4501542)
