Relative complexity of checking and evaluating

Cites work

General context-free recognition in less than cubic time
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?)
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

(96)

A low and a high hierarchy within NP
Strong nondeterministic polynomial-time reducibilities
Qualitative relativizations of complexity classes
Robust algorithms: a different approach to oracles
On some natural complete operators
NP is as easy as detecting unique solutions
One-way functions and circuit complexity
On hardness of one-way functions
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
Unambiguous computations and locally definable acceptance types
On gamma-reducibility versus polynomial time many-one reducibility
Reductions on NP and p-selective sets
On sets polynomially enumerable by iteration
Separating complexity classes with tally oracles
Turing machines with few accepting computations and low sets for PP
On polynomial time one-truth-table reducibility to a sparse set
Polynomial-time 1-Turing reductions from $\#$PH to $\#$P
Polynomial-time compression
On the power of enumerative counting
Graph isomorphism is low for PP
Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
A taxonomy of complexity classes of functions
Non-deterministic communication complexity with few witnesses
Recursion theoretic characterizations of complexity classes of counting functions
How to define a linear order on finite models
Approximation of boolean functions by combinatorial rectangles
A second step towards complexity-theoretic analogs of Rice's Theorem
Characterizing the existence of one-way permutations
On characterizing the existence of partial one-way permutations
Enumerative counting is hard
Tally NP sets and easy census functions.
Optimal series-parallel trade-offs for reducing a function to its own graph
One-way permutations and self-witnessing languages
Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
On the power of unambiguity in log-space
The complexity of identifying characteristic formulae
The robustness of LWPP and WPP, with an application to graph reconstruction
The opacity of backbones
On continuous one-way functions
A complexity theory for feasible closure properties
Collapsing degrees via strong computation
Quantum and classical complexity classes: Separations, collapses, and closure properties
Resource bounded immunity and simplicity
One-way functions and the nonisomorphism of NP-complete sets
Classes of bounded nondeterminism
Program size complexity of correction grammars in the Ershov hierarchy
On intractability of the classUP
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
On relativizations with restricted number of accesses to the oracle set
Immunity and simplicity in relativizations of probabilistic complexity classes
Immunity, simplicity, probabilistic complexity classes and relativizations
Simultaneous strong separations of probabilistic and unambiguous complexity classes
A survey of one-way functions in complexity theory
Structure and importance of logspace-MOD class
Structural analysis of the complexity of inverse functions
Restrictive Acceptance Suffices for Equivalence Problems
Computational tameness of classical non-causal models
The expressive power of unique total stable model semantics
The consequences of eliminating NP solutions
Fault-tolerance and complexity (extended abstract)
Implicit definability and infinitary logic in finite model theory (extended abstract)
On sets bounded truth-table reducible to P-selective sets
The Untold Story of $$\mathsf {SBP}$$
On the power of parity polynomial time
Graph isomorphism is low for PP
Promise problems and access to unambiguous computation
On the power of parity polynomial time
Counting classes: Thresholds, parity, mods, and fewness
Finding strongly popular $b$-matchings in bipartite graphs
Finding strongly popular $b$-matchings in bipartite graphs
Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
The complexity of computing the permanent
A map of witness maps: new definitions and connections
Intersection suffices for Boolean hierarchy equivalence
Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
Power of counting by nonuniform families of polynomial-size finite automata
Generalized implicit definitions on finite structures
On the power of counting the total number of computation paths of NPTMs
Power of counting by nonuniform families of polynomial-size finite automata
Finite-model theory -- A personal perspective
Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting
On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
Lower bounds and the hardness of counting properties
An oracle with no up-complete sets, but NP = PSPACE
Search versus search for collapsing electoral control types
Kolmogorov characterizations of complexity classes
On total functions, existence theorems and computational complexity
A note on quadratic residuosity and UP
Nondeterministic functions and the existence of optimal proof systems
Autoreducibility, mitoticity, and immunity
Robust machines accept easy sets
Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
The complexity of unions of disjoint sets

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)