Pages that link to "Item:Q4142696"
From MaRDI portal
The following pages link to Separating Nondeterministic Time Complexity Classes (Q4142696):
Displaying 33 items.
- A logical approach to locality in pictures languages (Q295631) (← links)
- A Turing machine time hierarchy (Q593780) (← links)
- Non-deterministic exponential time has two-prover interactive protocols (Q685724) (← links)
- Avoiding simplicity is complex (Q693072) (← links)
- Bounded-depth succinct encodings and the structure they imply on graphs (Q722204) (← links)
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes (Q756423) (← links)
- Deterministic two-way one-head pushdown automata are very powerful (Q800088) (← links)
- Time hierarchies for cryptographic function inversion with advice (Q843601) (← links)
- A uniform method for proving lower bounds on the computational complexity of logical theories (Q917543) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- k\(+1\) heads are better than k for PDAs (Q1109579) (← links)
- Dominoes and the complexity of subclasses of logical theories (Q1115859) (← links)
- On time-space classes and their relation to the theory of real addition (Q1155607) (← links)
- Bounded query machines: on NP and PSPACE (Q1158751) (← links)
- Some results on relativized deterministic and nondeterministic time hierarchies (Q1162808) (← links)
- Techniques for separating space complexity classes (Q1235979) (← links)
- Almost-everywhere complexity hierarchies for nondeterministic time (Q1261465) (← links)
- Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines (Q1323339) (← links)
- On P-immunity of exponential time complete sets (Q1362336) (← links)
- Space hierarchy theorem revised. (Q1401238) (← links)
- Local reduction (Q1641001) (← links)
- On relationships between complexity classes of Turing machines (Q1682916) (← links)
- Some consequences of the existnce of pseudorandom generators (Q1822961) (← links)
- Sparse sets and collapse of complexity classes (Q1854459) (← links)
- Verifying whether one-tape Turing machines run in linear time (Q2009635) (← links)
- Average-case rigidity lower bounds (Q2117087) (← links)
- Robust simulations and significant separations (Q2407096) (← links)
- The minimum oracle circuit size problem (Q2410683) (← links)
- A time lower bound for satisfiability (Q2581273) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- On the definitions of some complexity classes of real numbers (Q3310597) (← links)
- Towards separating nondeterminism from determinism (Q3334987) (← links)
- (Q5121894) (← links)
