Nonconstructive tools for proving polynomial-time decidability
- 1 June 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 35 (3) , 727-739
- https://doi.org/10.1145/44483.44491
Abstract
Recent advances in graph theory and graph algorithms dramatically alter the traditional view of concrete complexity theory, in which a decision problem is generally shown to be in P by producing an efficient algorithm to solve an optimization version of the problem. Nonconstructive tools are now available for classifying problems as decidable in polynomial time by guaranteeing only theexistenceof polynomial-timedecisionalgorithms. In this paper these new methods are employed to prove membership in P for a number of problems whose complexities are not otherwise known. Powerful consequences of these techniques are pointed out and their utility is illustrated. A type of partially ordered set that supports this general approach is defined and explored.Keywords
This publication has 20 references indexed in Scilit:
- Computers, trees and Abelian groupsComputers & Mathematics with Applications, 1988
- Nonconstructive advances in polynomial-time complexityInformation Processing Letters, 1987
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1987
- The Editor's Corner: Finite Lists of ObstructionsThe American Mathematical Monthly, 1987
- Exact and Approximate Solutions for the Gate Matrix Layout ProblemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Knots and links in spatial graphsJournal of Graph Theory, 1983
- Simply presented valuated abelian p-groupsJournal of Algebra, 1977
- Graph with given achromatic numberDiscrete Mathematics, 1976
- On well-quasi-ordering infinite treesMathematical Proceedings of the Cambridge Philosophical Society, 1965
- Bestimmung der Primfaktorzerlegung von VerkettungenMathematische Zeitschrift, 1961