Pages that link to "Item:Q1168733"
From MaRDI portal
The following pages link to Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis (Q1168733):
Displaying 50 items.
- Complexity and dimension (Q287068) (← links)
- NP-hard sets are superterse unless NP is small (Q290182) (← links)
- The strong exponential hierarchy collapses (Q584250) (← links)
- Infeasibility of instance compression and succinct PCPs for NP (Q619903) (← links)
- Separating NE from some nonuniform nondeterministic complexity classes (Q652627) (← links)
- A note on P-selective sets and closeness (Q673619) (← links)
- Bounded-depth succinct encodings and the structure they imply on graphs (Q722204) (← links)
- On small generators (Q802309) (← links)
- Kolmogorov characterizations of complexity classes (Q804291) (← links)
- Padding, commitment and self-reducibility (Q808694) (← links)
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) (Q859979) (← links)
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP (Q908700) (← links)
- New developments in structural complexity theory (Q913509) (← links)
- On the asymmetric complexity of the group-intersection problem (Q963437) (← links)
- A note on minimum-area upward drawing of complete and Fibonacci trees (Q970209) (← links)
- Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design (Q990937) (← links)
- On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts (Q1034609) (← links)
- On one-one polynomial time equivalence relations (Q1068536) (← links)
- Reductions among polynomial isomorphism types (Q1077412) (← links)
- On bounded query machines (Q1085975) (← links)
- A comparison of polynomial time completeness notions (Q1097692) (← links)
- On helping by robust oracle machines (Q1097695) (← links)
- Can the catenation of two weakly sparse languages be dense? (Q1102760) (← links)
- Isomorphisms and 1-L reductions (Q1107310) (← links)
- \(\Sigma_ 2SPACE(n)\) is closed under complement (Q1108795) (← links)
- Collapsing degrees (Q1109766) (← links)
- Relativized alternation and space-bounded computation (Q1111024) (← links)
- On the relative complexity of hard problems for complexity classes without complete problems (Q1112017) (← links)
- Notes on polynomial levelability (Q1119389) (← links)
- The complexity types of computable sets (Q1190982) (← links)
- Turing machines with few accepting computations and low sets for PP (Q1190987) (← links)
- On polynomial time one-truth-table reducibility to a sparse set (Q1191028) (← links)
- On polynomial-time Turing and many-one completeness in PSPACE (Q1193869) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- A note on sparse sets and the polynomial-time hierarchy (Q1263964) (← links)
- The structure of logarithmic advice complexity classes (Q1275000) (← links)
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis (Q1288202) (← links)
- On symmetric differences of NP-hard sets with weakly P-selective sets (Q1314375) (← links)
- On reductions of NP sets to sparse sets (Q1329162) (← links)
- The random oracle hypothesis is false (Q1333397) (← links)
- Space-efficient recognition of sparse self-reducible languages (Q1337147) (← links)
- Geometric sets of low information content (Q1351460) (← links)
- Quasi-linear truth-table reductions to \(p\)-selective sets (Q1351469) (← links)
- An excursion to the Kolmogorov random strings (Q1362331) (← links)
- Counting quantifiers, successor relations, and logarithmic space (Q1362332) (← links)
- Separating classes in the exponential-time hierarchy from classes in PH (Q1365687) (← links)
- On universally easy classes for NP-complete problems. (Q1401418) (← links)
- Resolution of Hartmanis' conjecture for NL-hard sparse sets (Q1575434) (← links)
- On hard instances (Q1575555) (← links)
- On the computational structure of the connected components of a hard problem (Q1607000) (← links)
