### sorai_nai's blog

By sorai_nai, 6 weeks ago,

Given is the following statement.

Given a Problem $P$, Let $T$ be the set of all testcases for this problem,

Let $t^* \in T$ be a test-case such that for a given program $S$, if $S$ passes the verdict of $t^*$, it's guranteed to pass $\forall \; t \in T$. ( Hence it's a correct solution.)

In simpler terms, Is it always possible to create a test-case for a problem, such that if a solution passes the verdict for that test-case, then it can claimed that the solution is correct.

Prove the existence/non-existence of $t^*$.

(i.e Prove that it exists, or prove that it doesn't.)

Note : The Given Problem P could be any problem. i.e Prove/Disprove it for all problems that could exist.

• -7

 » 6 weeks ago, # | ← Rev. 2 →   +27 It is wrong. You could have a problem for which there are two (or more) ways in which the program fails and a test can only check for one of them. For example, you are given two integers $1 \le a,b \le 10^9$ and you need to output $a+b,a-b,a \cdot b$ and $\frac{a}{b}$. One way in which a program may fail is from overflow. Additionally, one can put in his/her code this: if(a==82536234 || a==38475342) cout<<"foo"; It is impossible to check in one test both these cases.On the other hand, if you have a problem with multiple test cases per test, then you can cram every possible input in there and it will guarantee that the solution is correct.