The consequences of eliminating NP solutions

Achlioptas, 2005, Rigorous location of phase transitions in hard optimization problems, Nature, 435, 759, 10.1038/nature03602 Y. Bachrach, E. Elkind, Divide and conquer: False-name manipulations in weighted voting games, in: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, May 2008 (in press) Book, 1984, Quantitative relativizations of complexity classes, SIAM Journal on Computing, 13, 461, 10.1137/0213030 Braunstein, 2005, Survey propagation: An algorithm for satisfiability, Random Structures and Algorithms, 27, 201, 10.1002/rsa.20057 Buhrman, 1998, Functions computable with nonadaptive queries to NP, Theory of Computing Systems, 31, 77, 10.1007/s002240000079 Cai, 2005, Competing provers yield improved Karp–Lipton collapse results, Information and Computation, 198, 1, 10.1016/j.ic.2005.01.002 Cai, 1995, Communication complexity of key agreement on limited ranges, vol. 900, 38 Canetti, 1996, More on BPP and the polynomial-time hierarchy, Information Processing Letters, 57, 237, 10.1016/0020-0190(96)00016-6 Chandra, 1980, Computable queries for relational data bases, Journal of Computer and System Sciences, 21, 156, 10.1016/0022-0000(80)90032-X Chari, 1995, Randomness-optimal unique element isolation, with applications to perfect matching and related problems, SIAM Journal on Computing, 24, 1036, 10.1137/S0097539793250330 Chevaleyre, 2007, A short introduction to computational social choice Darwiche, 2002, A compiler for deterministic decomposable negation normal form, 627 Davies, 2007, Using more reasoning to improve #SAT solving, 185 Dubey, 1979, Mathematical properties of the Banzhaf power index, Mathematics of Operations Research, 4, 99, 10.1287/moor.4.2.99 Eiter, 2003, Answer set planning under action costs, Journal of Artificial Intelligence Research, 19, 25, 10.1613/jair.1148 P Faliszewski, E. Hemaspaandra, L. Hemaspaandra, J. Rothe, A richer understanding of the complexity of election systems, in: S. Ravi, S. Shukla (Eds.), Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz, Springer (in press). Preliminary version available as [17] P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, J. Rothe, A richer understanding of the complexity of election systems, Technical Report TR-903, Department of Computer Science, University of Rochester, Rochester, NY, September 2006 P. Faliszewski, L. Hemaspaandra, The complexity of power-index comparison, in: Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management, in Lecture Notes in Computer Science, Springer, 2008 (in press) P. Faliszewski, M. Ogihara, On the autoreducibility of functions, Technical Report TR-912, Department of Computer Science, University of Rochester, Rochester, NY, January 2007 Fenner, 1994, Gap-definable counting classes, Journal of Computer and System Sciences, 48, 116, 10.1016/S0022-0000(05)80024-8 Fenner, 1999, Complements of multivalued functions, Chicago Journal of Theoretical Computer Science, 1999 Fortnow, 1996, PP is closed under truth-table reductions, Information and Computation, 124, 1, 10.1006/inco.1996.0001 Garey, 1979 Gill, 1977, Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, 6, 675, 10.1137/0206049 Glaßer, 2005, Reductions between disjoint NP-pairs, Information and Computation, 200, 247, 10.1016/j.ic.2005.03.003 Goldschlager, 1986, On the construction of parallel computers from various bases of boolean functions, Theoretical Computer Science, 43, 43, 10.1016/0304-3975(86)90165-9 Gomes, 2005, Computational science: Can get satisfaction, Nature, 435, 751, 10.1038/435751a Greco, 2002, Search and optimization problems in Datalog, vol. 2408, 61 Gupta, 1992, On the closure of certain function classes under integer division by polynomially bounded functions, Information Processing Letters, 44, 205, 10.1016/0020-0190(92)90086-B Gupta, 1995, Closure properties and witness reduction, Journal of Computer and System Sciences, 50, 412, 10.1006/jcss.1995.1032 Han, 1997, Threshold computation and cryptographic security, SIAM Journal on Computing, 26, 59, 10.1137/S0097539792240467 Hemachandra, 1993, Is #P closed under subtraction?, 523 Hemaspaandra, 2007, Cluster computing and the power of edge recognition, Information and Computation, 205, 1274, 10.1016/j.ic.2007.02.001 Hemaspaandra, 2006, The complexity of computing the size of an interval, SIAM Journal on Computing, 36, 1264, 10.1137/S0097539705447013 Hemaspaandra, 1996, Computing solutions uniquely collapses the polynomial hierarchy, SIAM Journal on Computing, 25, 697, 10.1137/S0097539794268315 Hemaspaandra, 2002 Hemaspaandra, 2002, Reducing the number of solutions of NP functions, Journal of Computer and System Sciences, 64, 311, 10.1006/jcss.2001.1815 Hemaspaandra, 1998, Power balance and apportionment algorithms for the United States Congress, ACM Journal of Experimental Algorithmics, 3 Hemaspaandra, 2003 Hertrampf, 1995, On the power of number-theoretic operations with respect to counting, 299 Isobe, 2007, Toward separating integer factoring from discrete logarithm, IEICE Transactions on Communications, Electronics, Information, and Systems, E90-A, 48 Karp, 1980, Some connections between nonuniform and uniform complexity classes, 302 Ko, 1983, On self-reducibility and weak P-selectivity, Journal of Computer and System Sciences, 26, 209, 10.1016/0022-0000(83)90013-2 Köbler, 1989, On counting and approximation, Acta Informatica, 26, 363 Köbler, 2004, Average-case intractability vs. worst-case intractability, Information and Computation, 190, 1, 10.1016/j.ic.2003.05.002 Krentel, 1988, The complexity of optimization problems, Journal of Computer and System Sciences, 36, 490, 10.1016/0022-0000(88)90039-6 Ladner, 1975, On the structure of polynomial time reducibility, Journal of the ACM, 22, 155, 10.1145/321864.321877 Leone, 1999, On the complexity of search queries, 113 Long, 1982, Strong nondeterministic polynomial-time reducibilities, Theoretical Computer Science, 21, 1, 10.1016/0304-3975(82)90085-8 Mahajan, 1994, A note on SpanP functions, Information Processing Letters, 51, 7, 10.1016/0020-0190(94)00068-9 Matsui, 2001, NP-completeness for calculating power indices of weighted majority games, Theoretical Computer Science, 263, 305, 10.1016/S0304-3975(00)00251-6 A. Meyer, L. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, in: Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, October 1972, pp. 125–129 Mulmuley, 1987, Matching is as easy as matrix inversion, Combinatorica, 7, 105, 10.1007/BF02579206 Naik, 1998, A hierarchy based on output multiplicity, Theoretical Computer Science, 207, 131, 10.1016/S0304-3975(98)00060-7 Ogihara, 1996, Functions computable with limited access to NP, Information Processing Letters, 58, 35, 10.1016/0020-0190(96)00030-0 Ogihara, 1996, On closure properties of #P in the context of PF∘#P, Journal of Computer and System Sciences, 53, 171, 10.1006/jcss.1996.0059 Ogiwara, 1993, A complexity theory for feasible closure properties, Journal of Computer and System Sciences, 46, 295, 10.1016/0022-0000(93)90006-I Papadimitriou, 1983, Two remarks on the power of counting, vol. 145, 269 2006 Prasad, 1990, NP-completeness of some problems concerning voting games, International Journal of Game Theory, 19, 1, 10.1007/BF01753703 K. Regan, Enumeration problems. Manuscript, 1982; revised, 1985 Roth, 1996, On the hardness of approximate reasoning, Artificial Intelligence, 82, 273, 10.1016/0004-3702(94)00092-1 Russell, 1998, Symmetric alternation captures BPP, Computational Complexity, 7, 152, 10.1007/s000370050007 T. Sang, F. Bacchus, P. Beame, H. Kautz, T. Pitassi, Combining component caching and clause learning for effective model counting, in: Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing, May 2004, pp. 20–28 Selman, 1978, Polynomial time enumeration reducibility, SIAM Journal on Computing, 7, 440, 10.1137/0207035 Selman, 1994, A taxonomy of complexity classes of functions, Journal of Computer and System Sciences, 48, 357, 10.1016/S0022-0000(05)80009-1 Shapley, 1954, A method of evaluating the distribution of power in a committee system, American Political Science Review, 48, 787, 10.2307/1951053 J. Simon, On some central problems in computational complexity, Ph.D. Thesis, Cornell University, Ithaca, NY, January 1975. Available as Cornell Department of Computer Science Technical Report TR75-224 Stockmeyer, 1976, The polynomial-time hierarchy, Theoretical Computer Science, 3, 1, 10.1016/0304-3975(76)90061-X M. Thurley, Combining component caching and clause learning for effective model counting, in: Proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing, August 2006, pp. 424–429 Valiant, 1976, The relative complexity of checking and evaluating, Information Processing Letters, 5, 20, 10.1016/0020-0190(76)90097-1 Valiant, 1979, The complexity of computing the permanent, Theoretical Computer Science, 8, 189, 10.1016/0304-3975(79)90044-6 Valiant, 1979, The complexity of enumeration and reliability problems, SIAM Journal on Computing, 8, 410, 10.1137/0208032 Valiant, 1986, NP is as easy as detecting unique solutions, Theoretical Computer Science, 47, 85, 10.1016/0304-3975(86)90135-0 Vollmer, 1994, On different reducibility notions for function classes, vol. 775, 449 Wagner, 1986, The complexity of combinatorial problems with succinct input representations, Acta Informatica, 23, 325, 10.1007/BF00289117 Zankó, 1991, #P-completeness via many-one reductions, International Journal of Foundations of Computer Science, 2, 76, 10.1142/S0129054191000066