Pages that link to "Item:Q1109566"
From MaRDI portal
The following pages link to Complexity classes without machines: on complete languages for UP (Q1109566):
Displaying 44 items.
- Revisiting a result of Ko (Q286990) (← links)
- A characterization of the leaf language classes (Q287160) (← links)
- The strong exponential hierarchy collapses (Q584250) (← links)
- P-selectivity: Intersections and indices (Q673115) (← links)
- Kolmogorov characterizations of complexity classes (Q804291) (← links)
- A note on quadratic residuosity and UP (Q834917) (← links)
- Robust machines accept easy sets (Q914369) (← links)
- On the complexity of ranking (Q920620) (← links)
- Unambiguous computations and locally definable acceptance types (Q1127545) (← links)
- On sets polynomially enumerable by iteration (Q1176233) (← links)
- Separating complexity classes with tally oracles (Q1185002) (← links)
- A uniform approach to define complexity classes (Q1200807) (← links)
- Randomized Boolean decision trees: Several remarks (Q1275008) (← links)
- Optimal proof systems imply complete sets for promise classes (Q1398371) (← links)
- On universally easy classes for NP-complete problems. (Q1401418) (← links)
- On characterizing the existence of partial one-way permutations (Q1603545) (← links)
- Towards a unified complexity theory of total functions (Q1745728) (← links)
- Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
- On an optimal propositional proof system and the structure of easy subsets of TAUT. (Q1853507) (← links)
- One-way permutations and self-witnessing languages (Q1877694) (← links)
- The opacity of backbones (Q2051797) (← links)
- An oracle separating conjectures about incompleteness in the finite domain (Q2290649) (← links)
- Reductions between disjoint NP-pairs (Q2387199) (← links)
- LWPP and WPP are not uniformly gap-definable (Q2495405) (← links)
- Error-bounded probabilistic computations between MA and AM (Q2507698) (← links)
- Relativized counting classes: Relations among thresholds, parity, and mods (Q2638771) (← links)
- One-way functions and the nonisomorphism of NP-complete sets (Q2639055) (← links)
- A Parameterized Halting Problem (Q2908544) (← links)
- Do there exist complete sets for promise classes? (Q3107337) (← links)
- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes (Q3392941) (← links)
- On complete problems for \(NP\cap C_ 0NP\) (Q3696516) (← links)
- Complexity classes with complete problems between P and NP-C (Q3974851) (← links)
- Simultaneous strong separations of probabilistic and unambiguous complexity classes (Q3992020) (← links)
- Structural properties for feasibly computable classes of type two (Q4009811) (← links)
- Fault-tolerance and complexity (Extended abstract) (Q4630260) (← links)
- Towards a Unified Complexity Theory of Total Functions (Q4993302) (← links)
- An unambiguous class possessing a complete set (Q5048936) (← links)
- P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle (Q5092409) (← links)
- On the power of parity polynomial time (Q5096157) (← links)
- Promise problems and access to unambiguous computation (Q5096827) (← links)
- Approximate counting in bounded arithmetic (Q5422312) (← links)
- On the power of parity polynomial time (Q5750401) (← links)
- Dot operators (Q5958134) (← links)
- Intersection suffices for Boolean hierarchy equivalence (Q6085737) (← links)
