The Complexity of Recognizing Unique Sink Orientations
作者： Antonis Thomas , Bernd Gärtner
DOI: 10.4230/LIPICS.STACS.2015.341
关键词:
摘要: Given a Boolean Circuit with n inputs and outputs, we want to decide if it represents Unique Sink Orientation (USO). USOs are useful combinatorial objects that serve as abstraction of many relevant optimization problems. We prove recognizing USO is coNP-complete. However, the situation appears be more complicated for acyclic USOs. Firstly, give construction there exist cyclic where smallest cycle superpolynomial size. This implies straightforward representation (i.e. by list vertices) does not make up coNP certificate. Inspired this fact, investigate connection an PSPACE problem PSPACE-complete.
sci-hub.st 参考文章(18)
José L. Balcázar, Antoni Lozano, Jacobo Torán, The Complexity of Algorithmic Problems on Succinct Instances Computer Science. pp. 351- 377 ,(1992) , 10.1007/978-1-4615-3422-8_30
Bernd Gärtner, Leo Rüst, Simple stochastic games and p-matrix generalized linear complementarity problems fundamentals of computation theory. pp. 209- 220 ,(2005) , 10.1007/11537311_19
Ingo Schurr, Bernd Gärtner, Linear programming and unique sink orientations symposium on discrete algorithms. pp. 749- 757 ,(2006) , 10.5555/1109557.1109639
Alan Stickney, Layne Watson, Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem Mathematics of Operations Research. ,vol. 3, pp. 322- 333 ,(1978) , 10.1287/MOOR.3.4.322
Walter J. Savitch, Relationships between nondeterministic and deterministic tape complexities Journal of Computer and System Sciences. ,vol. 4, pp. 177- 192 ,(1970) , 10.1016/S0022-0000(70)80006-X
Hana Galperin, Avi Wigderson, Succinct representations of graphs Information & Computation. ,vol. 56, pp. 183- 198 ,(1984) , 10.1016/S0019-9958(83)80004-7
Nancy Lynch, Log Space Recognition and Translation of Parenthesis Languages Journal of the ACM. ,vol. 24, pp. 583- 590 ,(1977) , 10.1145/322033.322037
Tibor Szab�, Ingo Schurr, Finding the Sink Takes Some Time: An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes Discrete and Computational Geometry. ,vol. 31, pp. 627- 642 ,(2004) , 10.1007/S00454-003-0813-8
Jiří Matoušek, The Number Of Unique-Sink Orientations of the Hypercube* Combinatorica. ,vol. 26, pp. 91- 99 ,(2006) , 10.1007/S00493-006-0007-0
Kathy Williamson Hoke, Completely unimodal numberings of a simple polytope Discrete Applied Mathematics. ,vol. 20, pp. 69- 81 ,(1988) , 10.1016/0166-218X(88)90042-X