research-article

The Relative Complexity of NP Search Problems

Authors:

Russell Impagliazzo,

Toniann PitassiAuthors Info & Claims

Journal of Computer and System Sciences, Volume 57, Issue 1

Pages 3 - 19

https://doi.org/10.1006/jcss.1998.1575

Published: 01 August 1998 Publication History

Abstract

Papadimitriou introduced several classes of NP search problems based on combinatorial principles which guarantee the existence of solutions to the problems. Many interesting search problems not known to be solvable in polynomial time are contained in these classes, and a number of them are complete problems. We consider the question of the relative complexity of these search problem classes. We prove several separations which show that in a generic relativized world the search classes are distinct and there is a standard search problem in each of them that is not computationally equivalent to any decision problem. (Naturally, absolute separations would imply thatP NP.) Our separation proofs have interesting combinatorial content and go to the heart of the combinatorial principles on which the classes are based. We derive one result via new lower bounds on the degrees of poly- nomials asserted to exist by Hilbert's nullstellensatz over finite fields.

References

[1]

M. Blum, R. Implagliazzo, Generic oracles and oracle classes, Proceedings 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, October 1987, 118, 126

Digital Library

[2]

P. Beame, R. Implagliazzo, J. Krajíek, T. Pitassi, P. Pudlák, Lower bounds on Hilbert's nullstellensatz and propositional proofs, Proceedings 35th Annual IEEE Symposium on Foundations of Computer Science, Santa Fe, NM, November 1994, 794, 806

Digital Library

[3]

S.A. Cook, R. Impagliazzo, T. Yamakami, A tight relationship between generic oracles and type-2 complexity theory, Inform. & Comput., 137 (1997) 159-170.

Digital Library

[4]

M. Fellows, N. Koblitz, Self-witnessing polynomial-time complexity and prime factorization, Proceedings, Structure in Complexity Theory, Seventh Annual IEEE Conference, Boston, MA, June 1992, 107, 110

[5]

J. Hartmanis, L. A. Hemachandra, One-way functions, robustness, and nonisomorphism ofNP, Proceedings, Structure in Complexity Theory, Second Annual IEEE Conference, Cornell University, Ithaca, NY, June 1987, 160, 174

[6]

J. Hartmanis, L. Hemachandra, One-way functions, robustness, and non-isomorphism of NP-complete sets, Theor. Comput. Sci., 81 (1991) 155-163.

Digital Library

[7]

R. Impagliazzo, M. Naor, Decision trees and downward closures, Proceedings, Structure in Complexity Theory, Third Annual IEEE Conference, Washington, DC, June 1988, 29, 38

[8]

D.S. Johnson, C.H. Papadimitriou, M. Yannakakis, How easy is local search?, J. Comput. System Sci., 37 (1988) 79-100.

Digital Library

[9]

C. H. Papadimitriou, On graph-theoretic lemmata and complexity classes, Proceedings 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis, MO, October 1990, 794, 801

Digital Library

[10]

C. H. Papadimitriou, On inefficient proofs of existence and complexity classes, Proceedings of the 4th Czechoslovakian Symposium on Combinatorics, 1991

[11]

C.H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. System Sci., 48 (1994) 498-532.

Digital Library

[12]

V.R. Pratt, Every prime has a succinct sertificate, SIAM J. Comput., 4 (1975) 214-220.

[13]

C. H. Papadimitriou, A. A. Schäffer, M. Yannakakis, On the complexity of local search, Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, Baltimore, MD, May 1990, 438, 445

Digital Library

[14]

S. Riis, Independence in Bounded Arithmetic, Oxford University, 1993

[15]

G. Tardos, Query complexity, or why is it difficult to separateNPA¿coNPAby a random oracleA, Combinatorica, 9 (1989) 385-392.

[16]

M. Townsend, Complexity of type-2 relations, Notre Dame J. Formal Logic, 31 (1990) 241-262.

Cited By

Göös MHollender AJain SMaystre GPires WRobere RTao R(2024)Separations in Proof Complexity and TFNPJournal of the ACM10.1145/366375871:4(1-45)Online publication date: 9-May-2024
https://dl.acm.org/doi/10.1145/3663758
Fleming NGrosser SPitassi TRobere RMohar BShinkar IO'Donnell R(2024)Black-Box PPP Is Not Turing-ClosedProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649769(1405-1414)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649769
Kaufmann DFleury MBiere AKauers M(2024)Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-CheckerFormal Methods in System Design10.1007/s10703-022-00391-x64:1(73-107)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s10703-022-00391-x
Show More Cited By

Index Terms

The Relative Complexity of NP Search Problems
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...
Structural complexity of multiobjective NP search problems
LATIN'12: Proceedings of the 10th Latin American international conference on Theoretical Informatics

An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions.

There are at least two ...
Towards average-case complexity analysis of NP optimization problems
SCT '95: Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95)

For the worst-case complexity measure, if P=NP, then P=OptP, i.e., all NP optimization problems are polynomial-time solvable. On the other hand, it is not clear whether a similar relation holds when considering average-case complexity. We investigate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 57, Issue 1

Aug. 1998

123 pages

ISSN:0022-0000

Editor:
E. K. Blum
Univ. of Southern California, Los Angeles

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 August 1998

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Göös MHollender AJain SMaystre GPires WRobere RTao R(2024)Separations in Proof Complexity and TFNPJournal of the ACM10.1145/366375871:4(1-45)Online publication date: 9-May-2024
https://dl.acm.org/doi/10.1145/3663758
Fleming NGrosser SPitassi TRobere RMohar BShinkar IO'Donnell R(2024)Black-Box PPP Is Not Turing-ClosedProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649769(1405-1414)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649769
Kaufmann DFleury MBiere AKauers M(2024)Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-CheckerFormal Methods in System Design10.1007/s10703-022-00391-x64:1(73-107)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s10703-022-00391-x
Baillot PDal Lago UKop CVale D(2024)On Basic Feasible Functionals and the Interpretation MethodFoundations of Software Science and Computation Structures10.1007/978-3-031-57231-9_4(70-91)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57231-9_4
Davis BRobere R(2023)Colourful TFNP and Propositional ProofsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.36(1-21)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.36
Göös MHollender AJain SMaystre GPires WRobere RTao R(2022)Further collapses in TFNPProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.33(1-15)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.33
de Rezende SGöös MRobere R(2022)Guest ColumnACM SIGACT News10.1145/3532737.353274653:1(59-82)Online publication date: 20-Apr-2022
https://dl.acm.org/doi/10.1145/3532737.3532746
Bonacina IBonet M(2022)On the strength of Sherali-Adams and Nullstellensatz as propositional proof systemsProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533344(1-12)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533344
Hollender A(2022)The classes PPA-kTheoretical Computer Science10.1016/j.tcs.2021.06.016885:C(15-29)Online publication date: 22-Apr-2022
https://dl.acm.org/doi/10.1016/j.tcs.2021.06.016
Wang ZShen YLi SWang S(2022)A fine-grained fast parallel genetic algorithm based on a ternary optical computer for solving traveling salesman problemThe Journal of Supercomputing10.1007/s11227-022-04813-979:5(4760-4790)Online publication date: 30-Sep-2022
https://dl.acm.org/doi/10.1007/s11227-022-04813-9
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents