The following pages link to The complexity theory companion (Q5925718):
Displaying 39 items.
- The consequences of eliminating NP solutions (Q458458) (← links)
- Separating NE from some nonuniform nondeterministic complexity classes (Q652627) (← links)
- Inverse monoids associated with the complexity class NP (Q666698) (← links)
- Lower bounds and the hardness of counting properties (Q703531) (← links)
- Bernoulli measure on strings, and Thompson-Higman monoids. (Q766121) (← links)
- Time hierarchies for cryptographic function inversion with advice (Q843601) (← links)
- Complexity results in graph reconstruction (Q867853) (← links)
- The Boolean hierarchy of NP-partitions (Q924719) (← links)
- Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions (Q935140) (← links)
- On the asymmetric complexity of the group-intersection problem (Q963437) (← links)
- On the autoreducibility of functions (Q970103) (← links)
- Structural properties of oracle classes (Q990941) (← links)
- The complexity of satisfiability problems: Refining Schaefer's theorem (Q1015812) (← links)
- Theory of one-tape linear-time Turing machines (Q1041220) (← links)
- The isoperimetric spectrum of finitely presented groups (Q1630589) (← links)
- On the relative power of reduction notions in arithmetic circuit complexity (Q1679901) (← links)
- Towards implementation of a generalized architecture for high-level quantum programming language (Q1700813) (← links)
- Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
- The robustness of LWPP and WPP, with an application to graph reconstruction (Q2027204) (← links)
- A note on VNP-completeness and border complexity (Q2122788) (← links)
- Dichotomy results for fixed point counting in Boolean dynamical systems (Q2257296) (← links)
- Monomials in arithmetic circuits: complete problems in the counting hierarchy (Q2353185) (← links)
- On the connection between interval size functions and path counting (Q2410681) (← links)
- Rationalizations of Condorcet-consistent rules via distances of Hamming type (Q2450151) (← links)
- Out of order quantifier elimination for standard quantified linear programs (Q2456614) (← links)
- On a decision procedure for quantified linear programs (Q2462634) (← links)
- The complexity of two problems on arithmetic circuits (Q2465637) (← links)
- Quantum and classical complexity classes: Separations, collapses, and closure properties (Q2486397) (← links)
- LWPP and WPP are not uniformly gap-definable (Q2495405) (← links)
- On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant (Q2514144) (← links)
- All superlinear inverse schemes are coNP-hard (Q2575753) (← links)
- The Power of Self-Reducibility: Selectivity, Information, and Approximation (Q3297822) (← links)
- Polynomial-time right-ideal morphisms and congruences (Q4686444) (← links)
- Computation in generalised probabilisitic theories (Q5151582) (← links)
- (Q5216300) (← links)
- Infinitely generated semigroups and polynomial complexity (Q5739486) (← links)
- Robustness among multiwinner voting rules (Q5918366) (← links)
- Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets (Q5918833) (← links)
- Splitting NP-complete sets infinitely (Q6551699) (← links)
