2
$\begingroup$

A proof of $\mathsf{NP}$-completeness for a decision problem requires two things:

  • $\mathsf{NP}$ membership;
  • $\mathsf{NP}$-hardness.

It is often the case that the $\mathsf{NP}$-hardness part is the most difficult to prove, and it is not rare that some papers completely omit the $\mathsf{NP}$ membership part.

What I would like to ask is: is there a $\mathsf{NP}$-complete problem such that its $\mathsf{NP}$ membership via certificate existence is at least as difficult to prove than its $\mathsf{NP}$-hardness. For example, a primality certificate is not quite intuitive to find (but the primality decision problem is in $\mathsf{P}$, so it is not $\mathsf{NP}$-complete unless $\mathsf{P} = \mathsf{NP}$).

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think I've seen problems like this, but I'm having a hard time remembering specifics. I think it was a problem over the integers, and there was a non-trivial theorem that if any solution exists (i.e., any integer exists that solves the problem), then there exists a solution of polynomial size (i.e., there exists a solution where all the integers in the solution have bit-length that is polynomial in the input length). $\endgroup$
    – D.W. ♦
    Commented Nov 1, 2022 at 20:32
  • $\begingroup$ Going in the same direction: what about Integer linear programming? The intuition is that the coefficients of a solution could potentially be much larger than those of the input equations... For instance with $1 \leq x_1, 2x_1 \leq x_2, 2x_2 \leq x_3, \dots$ $\endgroup$
    – Charles Bouillaguet
    Commented Nov 9 at 19:18
  • $\begingroup$ @CharlesBouillaguet Indeed! See my other question where I had some problems with ILP. $\endgroup$
    – Nathaniel
    Commented Nov 9 at 19:50

1 Answer 1

Reset to default
1
$\begingroup$

Integer Linear Programming is such a problem.

  • Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$.
  • Question: is there a matrix $X\in \mathcal{M}_{n,1}(\mathbb{Z})$ such that $AX\leqslant B$? (the inequality being component by component).

An obvious certificate would be such a matrix $X$, but it is very hard to prove that there exists such an $X$ with size polynomial in the size of the input (indeed, the coefficient of $X$ could have a number of digits exponential in the number of digits of the coefficients of $A$ or $B$).

Improve this answer
$\endgroup$
2
  • $\begingroup$ No, The numbers can grow exponentially. The number of digits don't. $\endgroup$
    – gnasher729
    Commented Nov 11 at 9:14
  • $\begingroup$ @gnasher729 If the numbers grow exponentially, so do their numbers of digits… Indeed, the number of digits of $n$ is (roughly) $\log n$. The number of digits of $2^n$ is $n = 2^{\log n}$. $\endgroup$
    – Nathaniel
    Commented Nov 11 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.