Relative complexity of checking and evaluating
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3141365 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- General context-free recognition in less than cubic time
- Minimum partition of a matroid into independent subsets
- On the Computational Complexity of Algorithms
- On the computational power of pushdown automata
- Optimization of LR(k) parsers
- Proving simultaneous positivity of linear forms
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The complexity of theorem-proving procedures
Cited in
(91)- On characterizing the existence of partial one-way permutations
- On polynomial time one-truth-table reducibility to a sparse set
- One-way functions and circuit complexity
- The complexity of identifying characteristic formulae
- Optimal series-parallel trade-offs for reducing a function to its own graph
- Reductions on NP and p-selective sets
- Robust machines accept easy sets
- Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
- Structural analysis of the complexity of inverse functions
- A note on quadratic residuosity and UP
- Immunity, simplicity, probabilistic complexity classes and relativizations
- Separating complexity classes with tally oracles
- A survey of one-way functions in complexity theory
- Implicit definability and infinitary logic in finite model theory (extended abstract)
- The complexity of computing the permanent
- Generalized implicit definitions on finite structures
- On continuous one-way functions
- Nondeterministic functions and the existence of optimal proof systems
- Promise problems and access to unambiguous computation
- Finite-model theory -- A personal perspective
- Structure and importance of logspace-MOD class
- Enumerative counting is hard
- One-way permutations and self-witnessing languages
- Lower bounds and the hardness of counting properties
- Tally NP sets and easy census functions.
- On gamma-reducibility versus polynomial time many-one reducibility
- Approximation of boolean functions by combinatorial rectangles
- On intractability of the classUP
- Polynomial-time compression
- Finding strongly popular \(b\)-matchings in bipartite graphs
- Qualitative relativizations of complexity classes
- A taxonomy of complexity classes of functions
- Resource bounded immunity and simplicity
- Recursion theoretic characterizations of complexity classes of counting functions
- Turing machines with few accepting computations and low sets for PP
- Classes of bounded nondeterminism
- Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
- Immunity and simplicity in relativizations of probabilistic complexity classes
- A second step towards complexity-theoretic analogs of Rice's Theorem
- Unambiguous computations and locally definable acceptance types
- Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
- Kolmogorov characterizations of complexity classes
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- The robustness of LWPP and WPP, with an application to graph reconstruction
- Autoreducibility, mitoticity, and immunity
- Robust algorithms: a different approach to oracles
- Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
- Collapsing degrees via strong computation
- On sets bounded truth-table reducible to $P$-selective sets
- On helping by robust oracle machines
- Complexity classes without machines: on complete languages for UP
- On the relative complexity of hard problems for complexity classes without complete problems
- Counting classes: Thresholds, parity, mods, and fewness
- The consequences of eliminating NP solutions
- A map of witness maps: new definitions and connections
- On total functions, existence theorems and computational complexity
- On some natural complete operators
- Program size complexity of correction grammars in the Ershov hierarchy
- NP is as easy as detecting unique solutions
- On hardness of one-way functions
- Finding strongly popular \(b\)-matchings in bipartite graphs
- Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- On relativizations with restricted number of accesses to the oracle set
- Strong nondeterministic polynomial-time reducibilities
- On sets polynomially enumerable by iteration
- The opacity of backbones
- Fault-tolerance and complexity (extended abstract)
- Intersection suffices for Boolean hierarchy equivalence
- On the power of counting the total number of computation paths of NPTMs
- The Untold Story of $$\mathsf {SBP}$$
- The expressive power of unique total stable model semantics
- Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
- On the power of unambiguity in log-space
- Computational tameness of classical non-causal models
- On the power of enumerative counting
- How to define a linear order on finite models
- A low and a high hierarchy within NP
- The complexity of unions of disjoint sets
- One-way functions and the nonisomorphism of NP-complete sets
- Graph isomorphism is low for PP
- Non-deterministic communication complexity with few witnesses
- Graph isomorphism is low for PP
- On the power of parity polynomial time
- On the power of parity polynomial time
- A complexity theory for feasible closure properties
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- Restrictive Acceptance Suffices for Equivalence Problems
- Power of counting by nonuniform families of polynomial-size finite automata
- Characterizing the existence of one-way permutations
This page was built for publication: Relative complexity of checking and evaluating
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1232181)