A note on succinct representations of graphs
Information and ControlPublished 1 December 1986
Christos H. Papadimitriou, Mihalis Yannakakis
Citations186
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that under the same representation, graph properties that are ordinarily NP-complete become complete for non-deterministic exponential time.
Abstract
Galperin and Wigderson (Inform. and Control 56 (1983), 183–198) showed that certain trivial graph properties become NP-complete when the graph is represented in a particular exponentially succinct way. We show that under the same representation, graph properties that are ordinarily NP-complete become complete for non-deterministic exponential time.
Keywords
Computer ScienceEngineering
The complexity of theorem-proving procedures
6,107 Citations1971Stephen Cook
It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.
Theoretical Computer ScienceThe complexity of computing the permanent
2,759 Citations1979Leslie G. Valiant
It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations.
Theoretical Computer ScienceThe polynomial-time hierarchy
1,303 Citations1976Larry J. Stockmeyer
The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established.
ACM SIGACT NewsThe circuit value problem is log space complete for <i>P</i>
305 Citations1975Richard E. Ladner
The set P is the set of problems computable in polynomial_ time and the circuit value problem is CV, which is well known that a T(n) time bounded Turing machine can be simulate on n bits by a combinational circuit with 0(T-(n) gates.
Information and ControlSuccinct representations of graphs
219 Citations1983Hana Galperin, Avi Wigderson
The main result is characterizing a large class of graph properties for which the respective “succinct problem” is NP-hard, and shows that the succinct versions of polynomially equivalent problems may not be polynomial equivalent.
A complexity theory based on Boolean algebra
42 Citations1981Sven Skyum, Leslie G. Valiant