Pages that link to "Item:Q1232181"
From MaRDI portal
The following pages link to Relative complexity of checking and evaluating (Q1232181):
Displayed 50 items.
- Tight lower bounds on the ambiguity of strong, total, associative, one-way functions (Q596322) (← links)
- The complexity of computing the permanent (Q600247) (← links)
- Finite-model theory -- A personal perspective (Q688663) (← links)
- Lower bounds and the hardness of counting properties (Q703531) (← links)
- Kolmogorov characterizations of complexity classes (Q804291) (← links)
- On total functions, existence theorems and computational complexity (Q808245) (← links)
- Autoreducibility, mitoticity, and immunity (Q881593) (← links)
- Robust machines accept easy sets (Q914369) (← links)
- Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems (Q915446) (← links)
- Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions (Q935140) (← links)
- The complexity of unions of disjoint sets (Q955349) (← links)
- A low and a high hierarchy within NP (Q1052097) (← links)
- Strong nondeterministic polynomial-time reducibilities (Q1055405) (← links)
- Qualitative relativizations of complexity classes (Q1061119) (← links)
- Robust algorithms: a different approach to oracles (Q1063417) (← links)
- On some natural complete operators (Q1064780) (← links)
- NP is as easy as detecting unique solutions (Q1090454) (← links)
- One-way functions and circuit complexity (Q1096587) (← links)
- On hardness of one-way functions (Q1097693) (← links)
- On helping by robust oracle machines (Q1097695) (← links)
- Complexity classes without machines: on complete languages for UP (Q1109566) (← links)
- On the relative complexity of hard problems for complexity classes without complete problems (Q1112017) (← links)
- Unambiguous computations and locally definable acceptance types (Q1127545) (← links)
- On gamma-reducibility versus polynomial time many-one reducibility (Q1149766) (← links)
- Reductions on NP and p-selective sets (Q1166515) (← links)
- On sets polynomially enumerable by iteration (Q1176233) (← links)
- Separating complexity classes with tally oracles (Q1185002) (← links)
- Turing machines with few accepting computations and low sets for PP (Q1190987) (← links)
- On polynomial time one-truth-table reducibility to a sparse set (Q1191028) (← links)
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P (Q1193633) (← links)
- Polynomial-time compression (Q1198955) (← links)
- On the power of enumerative counting (Q1199550) (← links)
- Graph isomorphism is low for PP (Q1210331) (← links)
- Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory (Q1307703) (← links)
- A taxonomy of complexity classes of functions (Q1329166) (← links)
- Non-deterministic communication complexity with few witnesses (Q1337464) (← links)
- Recursion theoretic characterizations of complexity classes of counting functions (Q1365942) (← links)
- How to define a linear order on finite models (Q1371431) (← links)
- Approximation of boolean functions by combinatorial rectangles (Q1399979) (← links)
- A second step towards complexity-theoretic analogs of Rice's Theorem (Q1575716) (← links)
- Characterizing the existence of one-way permutations (Q1575721) (← links)
- On characterizing the existence of partial one-way permutations (Q1603545) (← links)
- Enumerative counting is hard (Q1822963) (← links)
- Tally NP sets and easy census functions. (Q1854340) (← links)
- Optimal series-parallel trade-offs for reducing a function to its own graph (Q1854508) (← links)
- One-way permutations and self-witnessing languages (Q1877694) (← links)
- Random parallel algorithms for finding exact branchings, perfect matchings, and cycles (Q1891230) (← links)
- A complexity theory for feasible closure properties (Q2366687) (← links)
- Collapsing degrees via strong computation (Q2366690) (← links)
- Quantum and classical complexity classes: Separations, collapses, and closure properties (Q2486397) (← links)