Pages that link to "Item:Q1394124"
From MaRDI portal
The following pages link to A hierarchy for nondeterministic time complexity (Q1394124):
Displaying 34 items.
- Graph properties checkable in linear time in the number of vertices (Q596315) (← links)
- Separating NE from some nonuniform nondeterministic complexity classes (Q652627) (← links)
- Bounded-depth succinct encodings and the structure they imply on graphs (Q722204) (← links)
- Cook reducibility is faster than Karp reducibility in NP (Q751812) (← links)
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes (Q756423) (← links)
- Time hierarchies for cryptographic function inversion with advice (Q843601) (← links)
- Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs (Q995752) (← links)
- Complexity lower bounds for machine computing models (Q1057651) (← links)
- Hierarchy of complexity of computation of partial functions with values 0 and 1 (Q1149431) (← links)
- Complexity results for classes of quantificational formulas (Q1157324) (← links)
- Bounded query machines: on NP and PSPACE (Q1158751) (← links)
- Comparing complexity classes (Q1227731) (← links)
- Techniques for separating space complexity classes (Q1235979) (← links)
- Toward a mathematical theory of graph-generative systems and its applications (Q1237578) (← links)
- Almost-everywhere complexity hierarchies for nondeterministic time (Q1261465) (← links)
- Classification of the index sets of low \([n]^ p\) and high \([n]^ p\) (Q1337641) (← links)
- First-order spectra with one binary predicate (Q1350533) (← links)
- Separating classes in the exponential-time hierarchy from classes in PH (Q1365687) (← links)
- Local reduction (Q1641001) (← links)
- Average-case rigidity lower bounds (Q2117087) (← links)
- Descriptive complexity of \#P functions: a new perspective (Q2220444) (← links)
- Unifying known lower bounds via geometric complexity theory (Q2351393) (← links)
- A time lower bound for satisfiability (Q2581273) (← links)
- On the Variable Hierarchy of First-Order Spectra (Q2957699) (← links)
- Towards separating nondeterminism from determinism (Q3334987) (← links)
- Universal quantifiers and time complexity of random access machines (Q3699679) (← links)
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP (Q3711750) (← links)
- Classifying the computational complexity of problems (Q3781088) (← links)
- Complexity classes and theories of finite models (Q3942945) (← links)
- Depth Reduction for Composites (Q4634033) (← links)
- Alternating time versus deterministic time: A separation (Q4717057) (← links)
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem (Q4957916) (← links)
- Separating NE from Some Nonuniform Nondeterministic Complexity Classes (Q5323096) (← links)
- Structure in average case complexity (Q6487946) (← links)
