Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
From MaRDI portal
Publication:1079364
DOI10.1016/0304-3975(85)90140-9zbMath0597.68042OpenAlexW2008585307WikidataQ56610696 ScholiaQ56610696MaRDI QIDQ1079364
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://digital.library.wisc.edu/1793/58504
SATpolynomially computable functionNP-complete setsk-creative setswitness functions for sets in NP and coNP
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items
Reductions among polynomial isomorphism types, One-way functions and the isomorphism conjecture, Collapsing degrees via strong computation, On one-way functions and polynomial-time isomorphisms, Scalability and the isomorphism problem, On simple and creative sets in NP, One-way functions and the nonisomorphism of NP-complete sets, Isomorphisms and 1-L reductions, DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization, The isomorphism conjecture holds and one-way functions exist relative to an oracle, Complexity classes without machines: on complete languages for UP, Collapsing degrees, Mathematical problems in cryptology, On the complexity of graph reconstruction, Notes on polynomial levelability, A survey of one-way functions in complexity theory, On the power of parity polynomial time, The degree structure of 1-L reductions, Promise problems and access to unambiguous computation, Speedup for natural problems and noncomputability, Polynomial-time axioms of choice and polynomial-time cardinality, Productive functions and isomorphisms, Kolmogorov complexity and degrees of tally sets, On sets polynomially enumerable by iteration, NP-Creative sets: A new class of creative sets in NP, On p-creative sets and p-completely creative sets, On the topological size of p-m-complete degrees, Oracles for structural properties: The isomorphism problem and public-key cryptography, Polynomial-time compression, On the power of parity polynomial time, On the autoreducibility of functions, Strong Reductions and Isomorphism of Complete Sets, Reductions to sets of low information content, Exponential-time and subexponential-time sets, Cook reducibility is faster than Karp reducibility in NP, Investigations Concerning the Structure of Complete Sets, On the p-isomorphism conjecture, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, On inefficient special cases of NP-complete problems, Resource bounded immunity and simplicity, Padding, commitment and self-reducibility
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial time computations in models of ET
- Reductions among polynomial isomorphism types
- Indexings of subrecursive classes
- A note on structure and looking back applied to the relative complexity of computable functions
- A uniform approach to obtain diagonal sets in complexity classes
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- Optimal Approximations and Polynomially Levelable Sets
- Completeness, Approximation and Density
- Optimal enumerations and optimal gödel numberings
- On the Structure of Polynomial Time Reducibility
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Simple Gödel Numberings, Isomorphisms, and Programming Properties
