Pages that link to "Item:Q1079364"
From MaRDI portal
The following pages link to Some remarks on witness functions for nonpolynomial and noncomplete sets in NP (Q1079364):
Displaying 41 items.
- Speedup for natural problems and noncomputability (Q620964) (← links)
- On the topological size of p-m-complete degrees (Q672460) (← links)
- Cook reducibility is faster than Karp reducibility in NP (Q751812) (← links)
- On the p-isomorphism conjecture (Q758202) (← links)
- Padding, commitment and self-reducibility (Q808694) (← links)
- Kolmogorov complexity and degrees of tally sets (Q916650) (← links)
- On the autoreducibility of functions (Q970103) (← links)
- Reductions among polynomial isomorphism types (Q1077412) (← links)
- On one-way functions and polynomial-time isomorphisms (Q1097694) (← links)
- On simple and creative sets in NP (Q1099614) (← links)
- Isomorphisms and 1-L reductions (Q1107310) (← links)
- Complexity classes without machines: on complete languages for UP (Q1109566) (← links)
- Collapsing degrees (Q1109766) (← links)
- Notes on polynomial levelability (Q1119389) (← links)
- On sets polynomially enumerable by iteration (Q1176233) (← links)
- On p-creative sets and p-completely creative sets (Q1183565) (← links)
- Oracles for structural properties: The isomorphism problem and public-key cryptography (Q1190988) (← links)
- Polynomial-time compression (Q1198955) (← links)
- Exponential-time and subexponential-time sets (Q1261474) (← links)
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem (Q1276160) (← links)
- One-way functions and the isomorphism conjecture (Q1329733) (← links)
- Scalability and the isomorphism problem (Q1351582) (← links)
- DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization (Q1362330) (← links)
- The isomorphism conjecture holds and one-way functions exist relative to an oracle (Q1362333) (← links)
- On inefficient special cases of NP-complete problems (Q1823688) (← links)
- Mathematical problems in cryptology (Q1910812) (← links)
- Collapsing degrees via strong computation (Q2366690) (← links)
- Resource bounded immunity and simplicity (Q2576870) (← links)
- One-way functions and the nonisomorphism of NP-complete sets (Q2639055) (← links)
- Investigations Concerning the Structure of Complete Sets (Q2821693) (← links)
- A survey of one-way functions in complexity theory (Q4009812) (← links)
- On the complexity of graph reconstruction (Q4298372) (← links)
- Productive functions and isomorphisms (Q4327382) (← links)
- NP-Creative sets: A new class of creative sets in NP (Q4895816) (← links)
- On the power of parity polynomial time (Q5096157) (← links)
- The degree structure of 1-L reductions (Q5096826) (← links)
- Promise problems and access to unambiguous computation (Q5096827) (← links)
- Reductions to sets of low information content (Q5204315) (← links)
- Strong Reductions and Isomorphism of Complete Sets (Q5458832) (← links)
- On the power of parity polynomial time (Q5750401) (← links)
- Polynomial-time axioms of choice and polynomial-time cardinality (Q6109071) (← links)
