0
$\begingroup$

Suppose that I have a polynomial-time algorithm to solve the graph embeddability problem.

$k$-embeddability problem :
Given an edge-weighted and undirected graph $G = (V,E)$, can we assign coordinates to each $v \in V$ in $k$-dimensions such that Euclidean distance between $u,v \in V$ is equal to the weight of the edge $\{u,v\}$?

And, suppose that I want to check if I have settled P vs. NP. The algorithm has 100% success rate when tested with random graphs.

However, I might be lucky while generating random data. Is there any finite set of test cases, such that if an algorithm solves each of them, that implies the algorithm is able to solve graph-embedding problem for all possible problem instances?

(I've already verified that the algorithm runs in polynomial time; now I just want to verify whether the algorithm is correct.)

$\endgroup$
2
  • $\begingroup$ @D.W. I already have an algorithm that runs in polynomial-time. I just want to know if the algorithm can actually solve all instances of the problem. Of course, I cannot test with infinitely many instances, but can I somehow find some extreme test cases which shows that the algorithm is correct? $\endgroup$
    – padawan
    Mar 11, 2016 at 9:49
  • $\begingroup$ For question 1, I have made an edit. And for 2, I have updated the link to a research paper that proves $k$-embeddability problem is strongly NP-hard. $\endgroup$
    – padawan
    Mar 11, 2016 at 10:05

1 Answer 1

4
+50
$\begingroup$

No finite set of test cases can prove correctness of an algorithm, if we have no information about the form or structure of the algorithm and if the set of possible inputs is infinite.

For any finite set of test cases you might have in mind, I can come up with an algorithm that works correctly on all of those test cases, but is incorrect (works incorrectly on another input, or on infinitely many inputs). For instance, if your test cases are the inputs $t_1,\dots,t_k$, and the correct answers are $y_1,\dots,y_k$, then my algorithm can be:

Algorithm FooledYou(x):
1. If $x=t_i$ for some $i$, then output $y_i$. Otherwise, output 42.

This algorithm has polynomial time and works correctly on those $k$ test cases, but is not a correct solution to the problem.

This is a fundamental limitation of using testing to check program correctness. Testing cannot prove a program is correct; it can only prove the program is incorrect.


Now, suppose you want to test your program in practice. Here is a heuristic that will likely be effective. You link to a paper that shows that 1-embeddability is strongly NP-complete, by showing a polynomial-time reduction from 3SAT to 1-embeddability. There are standard ways of generating hard instances of 3SAT. So, use that polynomial-time reduction to convert them into (hard) instances of 1-embeddability, and test whether your algorithm gives a correct answer and solves the corresponding 3SAT problem. Odds are, this will reveal a problem of some sort somewhere.

For instance, one standard way to generate hard 3SAT instances is by using the reduction from Factoring to 3SAT: generate a random 2048-bit RSA modulus (product of two 1024-bit primes), then ask what its factors are. For more details, see Fast Reduction from RSA to SAT and Generating 3SAT circuit for Integer factorization example.

$\endgroup$
1

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.