5
$\begingroup$

Lets say I have a computer program below.

(define (factorial x)
   (if (= x 0)
       1
       (else (* x (factorial (- x 1)))))

I then take each line of the program and create a random permutation.

       1
   (if (= x 0)
       (else (* x (factorial (- x 1)))))
(define (factorial x)

Now I give you a set of valid values that the program must return. 1,2,6,24

Your task is to sort the permutations of the program until it gives you the result.

Is this a new problem? I haven't found anything remotely like the problem I proposed above.

What is the runtime to solving this problem?

$\endgroup$
  • $\begingroup$ In almost all cases where your program is more than 5-6 lines, there will only be a handful permutations that compile and return values? As you increase the complexity of the program, the permutations will decrease dramatically too. $\endgroup$ – Konstantinos Koiliaris Aug 13 '18 at 16:24
  • $\begingroup$ @KonstantinosKoiliaris Yea so worst case runtime would be O(N!) * O(C) where N is the amount of lines and C is the run time of the program. $\endgroup$ – Joshua Herman Aug 13 '18 at 17:23
  • 2
    $\begingroup$ Brute force, you’d have to try all O(N!) permutations, but the run time of the program is not guaranteed to terminate for any random permutation (halting problem). So, wouldn’t that make the problem undecidable? $\endgroup$ – Konstantinos Koiliaris Aug 13 '18 at 17:26
  • 1
    $\begingroup$ This is surely undecidable in most programming languages -- as you can modify any given program P so that the only permutation that is syntactically correct is equivalent to P, and so solving the problem for the modified program could tell you whether running P ever returns, say, 0. Which is undecidable. $\endgroup$ – Neal Young Aug 17 '18 at 0:32
6
$\begingroup$

This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$.

(Of course, that does not guarantee that you found the correct permutation for input 5.)

Specific running time estimates may depend on the programming language being used. For instance, in BASIC each line is supposed to start with a line number which makes this solvable in polynomial time.

$\endgroup$
  • $\begingroup$ It seems your solution assumes that it is provided as a promise that one of the permutations outputs $1, 2, 6, 24$ on inputs $1, 2, 3, 4$? $\endgroup$ – C Komus Aug 14 '18 at 8:17
  • 1
    $\begingroup$ Why is it decidable? It seems to me that it is only semi-decidable, as some of the permutations may run forever and we won't be able to tell. $\endgroup$ – Andrej Bauer Aug 15 '18 at 12:42
  • 1
    $\begingroup$ I would say semidecidable. “Computable” is too vague and if anything it means decidable (to me at least). $\endgroup$ – Andrej Bauer Aug 15 '18 at 19:47
  • 1
    $\begingroup$ @AndrejBauer fair enough, it's a partial recursive function $\endgroup$ – Bjørn Kjos-Hanssen Aug 15 '18 at 20:03
  • 1
    $\begingroup$ @CKomus right, we're just discussing which words are appropriate for that case $\endgroup$ – Bjørn Kjos-Hanssen Aug 17 '18 at 16:03
3
$\begingroup$

Others have pointed out this is semidecidable. In most programming languages, the problem is NP-hard. In particular, the following problem is NP-hard:

Input: a set of lines of code
Question: does there exist a permutation, so that this yields a syntactically valid program?

If the programming language has two kinds of matched parentheses (e.g., () and []), then the problem is NP-hard, as shown here, as we can restrict to programs that contain only those symbols. Most languages have at least two kinds of parentheses symbols (e.g., () or [] or {}).

(Even in a language as simple as Scheme, it might still be possible to encode two independent types of parenthesis symbols: e.g., let (# and t) be the first pair of symbols, and (if #t and   1) be the other pair of symbols.)

$\endgroup$
  • $\begingroup$ @NealYoung, you're right; corrected. $\endgroup$ – D.W. Aug 17 '18 at 1:20
  • $\begingroup$ (Deleting my other comment given the updated post.) Here's another way to show it is NP hard: given a SAT formula, produce a program P that has no syntactically correct permutation (other than the identity) and that outputs "True" if and only if the formula is satisfiable. $\endgroup$ – Neal Young Aug 17 '18 at 3:27
  • $\begingroup$ @NealYoung, that sounds interesting. I'd be interested to see how to construct such a program. $\endgroup$ – D.W. Aug 17 '18 at 3:54
  • 2
    $\begingroup$ E.g. make a single-line program that checks all possible assignments and returns 0 iff there is a satisfying assignment. $\endgroup$ – Neal Young Aug 17 '18 at 14:52
1
$\begingroup$

At first not all the permutations will lead to a valid program. secondly, the answer depend on how the code is formatted.

next, there could be permutations that produce a program that do not terminate making it impossible to know if the output correspond to the valid values you gave. for instance suppose you have formatted your previous program as follow:

(define (factorial x)
   (if (= x 0)
       1
       (else 
         (* x (factorial (- x 1)))
    ))

and consider the following permutation of its lines:

(define (factorial x)
   (* x (factorial (- x 1)))
    (if (= x 0)
       1
       (else              
    ))

it is clear that it will not terminate.

As a result it cannot be possible to give the run time needed to solve it in the general case.

$\endgroup$
  • 2
    $\begingroup$ I agree with your conclusion but not your reasoning. (It's true that the obvious approach -- executing each permutation -- doesn't work for the reason you point out, but that does not imply that no approach works. For that you need a more careful argument.) $\endgroup$ – Neal Young Aug 17 '18 at 0:35
  • $\begingroup$ The difficulty is that if we want to know that a permuted program produces the right output, then we shall execute it and compare its output with the correct one. However this latter is not guaranteed to terminate. $\endgroup$ – RTK Aug 17 '18 at 7:11
  • $\begingroup$ Sure but you then conclude "it cannot be possible" (by any means, presumably), which does not follow from your argument. $\endgroup$ – Neal Young Aug 17 '18 at 14:53

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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