Graph Isomorphism Problem - Program Checking

Program Checking

Blum and Kannan have shown a program checker for graph isomorphism. Suppose P is a claimed polynomial-time procedure that checks if two graphs are isomorphic, but it is not trusted. To check if G and H are isomorphic:

  • Ask P whether G and H are isomorphic.
    • If the answer is "yes':
      • Attempt to construct an isomorphism using P as subroutine. Mark a vertex u in G and v in H, and modify the graphs to make them distinctive (with a small local change). Ask P if the modified graphs are isomorphic. If no, change v to a different vertex. Continue searching.
      • Either the isomorphism will be found (and can be verified), or P will contradict itself.
    • If the answer is "no":
      • Perform the following 100 times. Choose randomly G or H, and randomly permute its vertices. Ask P if the graph is isomorphic to G and H. (As in AM protocol for graph nonisomorphism).
      • If any of the tests are failed, judge P as invalid program. Otherwise, answer "no".

This procedure is polynomial-time and gives the correct answer if P is a correct program for graph isomorphism. If P is not a correct program, but answers correctly on G and H, the checker will either give the correct answer, or detect invalid behaviour of P. If P is not a correct program, and answers incorrectly on G and H, the checker will detect invalid behaviour of P with high probability, or answer wrong with probability 2-100.

Notably, P is used only as a blackbox.

Read more about this topic:  Graph Isomorphism Problem

Famous quotes containing the word program:

    Along the highway, all but lost among blatant neon lights flashing ‘Whiskey’ and ‘Dance and Dine,’ are crudely daubed warnings erected by itinerant evangelists, announcing that ‘Jesus is soon coming,’ or exhorting the traveler to ‘prepare to meet thy God.’
    —For the State of Florida, U.S. public relief program (1935-1943)