Pages that link to "Item:Q1090455"
From MaRDI portal
The following pages link to The complexity of combinatorial problems with succinct input representation (Q1090455):
Displayed 50 items.
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy (Q685431) (← links)
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory (Q685716) (← links)
- Lower bounds and the hardness of counting properties (Q703531) (← links)
- Probabilistic polynomial time is closed under parity reductions (Q751270) (← links)
- An oracle separating \(\oplus P\) from \(PP^{PH}\) (Q751272) (← links)
- Semidefinite programming and arithmetic circuit evaluation (Q943844) (← links)
- Efficient verification of Tunnell's criterion (Q957686) (← links)
- Some observations on the connection between counting and recursion (Q1098837) (← links)
- Parallel computation with threshold functions (Q1107324) (← links)
- More complicated questions about maxima and minima, and some closures of NP (Q1107524) (← links)
- The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) (Q1118407) (← links)
- Unambiguous computations and locally definable acceptance types (Q1127545) (← links)
- On matroids and hierarchical graphs (Q1178207) (← links)
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems (Q1185244) (← links)
- Restricted relativizations of probabilistic polynomial time (Q1186606) (← links)
- Turing machines with few accepting computations and low sets for PP (Q1190987) (← links)
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P (Q1193633) (← links)
- Generalizations of Opt P to the polynomial hierarchy (Q1193867) (← links)
- A note on the permanent value problem (Q1198001) (← links)
- On the power of enumerative counting (Q1199550) (← links)
- A uniform approach to define complexity classes (Q1200807) (← links)
- On the closure of certain function classes under integer division by polynomially-bounded functions (Q1208441) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- Graph isomorphism is low for PP (Q1210331) (← links)
- Succinct representation, leaf languages, and projection reductions (Q1271623) (← links)
- Succinctness as a source of complexity in logical formalisms (Q1302307) (← links)
- Gap-definable counting classes (Q1318473) (← links)
- A note on SpanP functions (Q1328756) (← links)
- Simple characterizations of \(P(\# P)\) and complete problems (Q1333395) (← links)
- On closure properties of GapP (Q1337146) (← links)
- Universally serializable computation (Q1384538) (← links)
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits (Q1567407) (← links)
- Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
- Complexity results for structure-based causality. (Q1852862) (← links)
- Nonerasing, counting, and majority over the linear time hierarchy (Q1854524) (← links)
- A complexity theory for feasible closure properties (Q2366687) (← links)
- Quantum and classical complexity classes: Separations, collapses, and closure properties (Q2486397) (← links)
- A parametric analysis of the state-explosion problem in model checking (Q2495399) (← links)
- Subtractive reductions and complete problems for counting complexity classes (Q2566034) (← links)
- Relativized counting classes: Relations among thresholds, parity, and mods (Q2638771) (← links)
- SeparatingPH fromPP by relativization (Q4025322) (← links)
- On the power of deterministic reductions to C=P (Q4032933) (← links)
- Immunity and Simplicity for Exact Counting and Other Counting Classes (Q4265536) (← links)
- Generalized theorems on relationships among reducibility notions to certain complexity classes (Q4298368) (← links)
- On the complexity of graph reconstruction (Q4298372) (← links)
- Restrictive Acceptance Suffices for Equivalence Problems (Q4504964) (← links)
- Bounded queries to arbitrary sets (Q4717045) (← links)
- On the power of generalized Mod-classes (Q4864444) (← links)
- Relationships among $PL$, $\#L$, and the determinant (Q4889814) (← links)
- A relationship between difference hierarchies and relativized polynomial hierarchies (Q5289273) (← links)