Test cases for graph embeddability problem

Question

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.)

Answer 1

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.