0
$\begingroup$

I hope this question is not out of place here, but I am currently attempting to implement the problem(a reduction algorithm) stated in the Title. I included the steps I am following as of now and an existing attempt at implementation. Are there better/simpler ways to go about this? Logic: Create a non-deterministic Turing machine that accepts if there exists a factor of n less than k, and rejects otherwise. This Turing machine could be implemented using a set of states, transition rules, and a way of storing and reading input and output. For example, the machine could have a start state, an accept state, and a reject state. It could also have a set of intermediate states for carrying out the binary search for a factor of n within the range 1 to k. The transition rules would specify how the machine moves from one state to another based on the current input and the state it is in. The input would be the values of n and k, and the output would be whether the machine accepts or rejects the input.

Use the Cook-Levin reduction to construct a boolean circuit that is satisfiable if and only if the Turing machine accepts the input (n,k). This would involve defining the circuit using logical gates and connections, and ensuring that it has the desired behavior. The Cook-Levin reduction is a method for constructing a boolean circuit that is satisfiable if and only if a given Turing machine accepts its input. This means that the circuit will have the same behavior as the Turing machine, in terms of whether it accepts or rejects a given input. To construct the circuit, we would need to specify the logical gates and connections that make up the circuit, and ensure that they are arranged in such a way that the circuit is satisfiable if and only if the Turing machine accepts the input.

Convert the boolean circuit into a formula using the reduction from Circuit-SAT to 3-SAT. This would involve expressing the circuit as a logical formula using variables and logical operators, in a way that is equivalent to the behavior of the original circuit. The reduction from Circuit-SAT to 3-SAT is a method for converting a boolean circuit into a logical formula that is satisfiable if and only if the original circuit is satisfiable. This means that the formula will have the same behavior as the original circuit, in terms of whether it is satisfiable for a given input. To convert the circuit into a formula, we would need to express the logical gates and connections of the circuit using logical operators and variables, and ensure that the resulting formula is equivalent to the behavior of the original circuit.

Convert the formula into a graph using the reduction from 3-SAT to Hamiltonian Path. This would involve representing the formula as a graph, with vertices and edges, in a way that is equivalent to the behavior of the original formula. The reduction from 3-SAT to Hamiltonian Path is a method for converting a logical formula into a graph that has a Hamiltonian path if and only if the original formula is satisfiable. This means that the graph will have the same behavior as the original formula, in terms of whether it has a Hamiltonian path for a given input. To convert the formula into a graph, we would need to represent the logical variables and operators of the formula as vertices and edges of the graph, and ensure that the resulting graph is equivalent to the behavior of the original formula.

(Last and easy part) Use a Hamiltonian Path oracle to determine whether the graph has a Hamiltonian path. This could be implemented using an algorithm or other tool that is able to determine whether a given graph has a Hamiltonian path.

class TuringMachine:
    # initialize the Turing machine with the values of n and k
    def __init__(self, n, k):
        self.n = n
        self.k = k
        self.initial_state = None
        self.accept_state = None
        self.reject_state = None
        self.transition_rules = {}

    # set the initial state of the Turing machine
    def set_initial_state(self, state):
        self.initial_state = state

    # set the accept state of the Turing machine
    def set_accept_state(self, state):
        self.accept_state = state

    # set the reject state of the Turing machine
    def set_reject_state(self, state):
        self.reject_state = state

    # add a transition rule to the Turing machine
    def add_transition_rule(self, state, input, next_state, output):
        # initialize the dictionary for the given state if it does not exist
        if state not in self.transition_rules:
            self.transition_rules[state] = {}

        # add the transition rule to the dictionary for the given state
        self.transition_rules[state][input] = (next_state, output)

    # execute the Turing machine on the given input and return the result
    def execute(self, input):
        # set the current state to the initial state
        current_state = self.initial_state

        # while the current state is not the accept or reject state,
        # execute the transition rules based on the current input
        while current_state != self.accept_state and current_state != self.reject_state:
            next_state, output = self.transition_rules[current_state][input]
            current_state = next_state
            input = output

        # return the result of the Turing machine execution
        if current_state == self.accept_state:
            return "accept"
        else:
            return "reject"

    # return a string representation of the Turing machine
    def __str__(self):
        # create a string representation of the Turing machine
        tm_str = "Turing Machine:\n"
        tm_str += "  Initial state: " + str(self.initial_state) + "\n"
        tm_str += "  Accept state: " + str(self.accept_state) + "\n"
        tm_str += "  Reject state: " + str(self.reject_state) + "\n"
        tm_str += "  Transition rules:\n"
        for state in self.transition_rules:
            for input in self.transition_rules[state]:
                next_state, output = self.transition_rules[state][input]
                tm_str += "    " + str(state) + " on " + str(input) + " => " + str(next_state) + " with output " + str(output) + "\n"
         # return the string representation of the Turing machine
        return tm_str

    # set the initial state of the Turing machine
    def set_initial_state(self, state):
        self.initial_state = state

    # set the accept state of the Turing machine
    def set_accept_state(self, state):
        self.accept_state = state

    # set the reject state of the Turing machine
    def set_reject_state(self, state):
        self.reject_state = state

    # add a transition rule to the Turing machine
    def add_transition_rule(self, state, input, next_state, output):
        self.transition_rules[state][input] = (next_state, output)

    # execute the Turing machine on the given input and return the result
    def execute(self, input):
        # set the current state to the initial state
        current_state = self.initial_state

        # while the current state is not the accept or reject state,
        # execute the transition rules based on the current input
        while current_state != self.accept_state and current_state != self.reject_state:
            next_state, output = self.transition_rules[current_state][input]
            current_state = next_state
            input = output

        # return the result of the Turing machine execution
        if current_state == self.accept_state:
            return "accept"
        else:
            return "reject"
# define the function for performing a depth-first search
def dfs(vertex, visited, vertices):
    # perform a depth-first search on the given vertex and return the result
    visited.add(vertex)
    if len(visited) == len(vertices):
        return True
    for neighbor in vertex.neighbors:
        if neighbor not in visited:
            has_path = dfs(neighbor, visited, vertices)
            if has_path:
                return True
    return False

# define the function for checking if a graph has a Hamiltonian path
def check_for_hamiltonian_path(graph):
    # check if the graph has a Hamiltonian path and return the result
    has_path = False
    for vertex in graph.vertices:
        visited = set()
        has_path = dfs(vertex, visited, graph.vertices)
        if has_path:
            break
    return has_path
# define the Graph class for representing a graph
class Graph:
    # initialize the graph with a list of vertices
    def __init__(self, vertices):
        self.vertices = vertices

    # add a vertex to the graph
    def add_vertex(self, vertex):
        self.vertices.append(vertex)

    # add an edge to the graph
    def add_edge(self, vertex1, vertex2):
        self.vertices[vertex1].add_neighbor(vertex2)
        self.vertices[vertex2].add_neighbor(vertex1)
    def has_hamiltonian_path(self):
        # check if the graph has a Hamiltonian path and return the result
        has_path = check_for_hamiltonian_path(self)
        return has_path

# define the states of the Turing machine
START = "Start"
ACCEPT = "Accept"
REJECT = "Reject"
# define the function for constructing a boolean circuit using the Cook-Levin reduction
def cook_levin_algorithm(clauses):
    # create an empty list to store the variables in the boolean circuit
    variables = []

    # for each clause in the list of clauses, add the variables in the clause to the list of variables
    for clause in clauses:
        for variable in clause:
            if variable != 0:
                variables.append(variable)

    # create the boolean circuit using the list of variables and clauses and return the result
    circuit = create_circuit(variables, clauses)
    return circuit
# define the function for constructing a boolean circuit using the Cook-Levin reduction
def cook_levin(n, k):
    # create an empty list to store the clauses in the boolean circuit
    clauses = []

    # for each value of i from 1 to n, create a clause that represents the value of x_i
    for i in range(1, n+1):
        clause = (i, i, 0)
        clauses.append(clause)

    # create a clause that represents the negation of the value of x_n+1 (the accept state)
    clause = (n+1, 0, 0)
    clauses.append(clause)

    # for each value of i from 1 to k, create a clause that represents the transition from state x_i
    # to state x_i+1
    for i in range(1, k+1):
        clause = (i, i+1, 0)
        clauses.append(clause)

    # create a clause that represents the transition from state x_k+1 (the reject state)
    # to state x_k+1 (the reject state)
    clause = (k+1, k+1, 0)
    clauses.append(clause)

    # create the boolean circuit using the clauses and return the result
    circuit = cook_levin_algorithm(clauses)
    return circuit
# define the function for creating a formula in conjunctive normal form (CNF)
def cnf(clauses):
    # create the formula in CNF using the list of clauses and return the result
    formula = "&".join(clauses)
    return formula

# define the function for creating a formula using the Circuit-SAT reduction
def create_formula(clauses):
    # create the formula using the list of clauses and return the result
    formula = cnf(clauses)
    return formula
# define the function for converting a boolean circuit into a formula using the Circuit-SAT reduction
def circuit_sat(circuit):
    # create an empty list to store the clauses in the formula
    clauses = []

    # for each gate in the boolean circuit, create a clause that represents the output of the gate
    # based on the inputs to the gate
    for gate in circuit:
        # get the inputs and output of the gate
        inputs = gate[0]
        output = gate[1]

        # create a clause that represents the output of the gate based on the inputs
        clause = (inputs[0], inputs[1], -output)
        clauses.append(clause)

    # create the formula using the clauses and return the result
    formula = create_formula(clauses)
    return formula

def create_circuit(n, k):
    # create the boolean circuit for the given input (n, k) using the Cook-Levin theorem
    circuit = cook_levin(n, k)
    return circuit

# define the function for converting a boolean circuit into a formula using the Circuit-SAT reduction
def convert_to_formula(circuit):
    # convert the given boolean circuit into a formula in conjunctive normal form (CNF)
    # using the Circuit-SAT reduction
    formula = circuit_sat(circuit)
    return formula

# define the function for creating a vertex that represents a clause in a formula
def clause_to_vertex(clause):
    # create the vertex that represents the clause and return the result
    vertex = ",".join(clause)
    return vertex

# define the function for creating a graph from a list of vertices
def create_graph_from_vertices(vertices):
    # create the graph using the list of vertices and return the result
    graph = Graph(vertices)
    return graph

# define the function for creating a vertex that represents a clause in a formula
def create_vertex(clause):
    # create the vertex that represents the clause and return the result
    vertex = clause_to_vertex(clause)
    return vertex

# define the function for creating a graph from a list of vertices
def create_graph(vertices):
    # create the graph using the list of vertices and return the result
    graph = create_graph_from_vertices(vertices)
    return graph
# define the function for converting a formula into a graph using the 3-SAT reduction
def three_sat(formula):
    # create an empty list to store the vertices in the graph
    vertices = []

    # for each clause in the formula, create a vertex that represents the clause
    for clause in formula:
        vertex = create_vertex(clause)
        vertices.append(vertex)

    # create the graph using the list of vertices and return the result
    graph = create_graph(vertices)
    return graph


# define the function for converting a formula into a graph using the 3-SAT reduction
def convert_to_graph(formula):
    # convert the given formula into a graph using the 3-SAT reduction
    graph = three_sat(formula)
    return graph


# define the function for checking if a graph has a Hamiltonian path
def hamiltonian_path(graph):
    # check if the graph has a Hamiltonian path and return the result
    has_path = graph.has_hamiltonian_path()
    return has_path
# define the function for using a Hamiltonian Path oracle to determine whether a graph has a Hamiltonian path
def oracle(graph):
    # use the Hamiltonian Path oracle to determine whether the given graph has a Hamiltonian path
    result = hamiltonian_path(graph)
    return result
# define the function for constructing a boolean circuit using the Cook/Levin reduction
def cook_levin_reduction(n, k):
    # create the boolean circuit for the given input (n, k)
    circuit = create_circuit(n, k)
    return circuit

# define the function for converting a boolean circuit into a formula using the Circuit-SAT reduction
def circuit_sat_reduction(circuit):
    # convert the given boolean circuit into a formula
    formula = convert_to_formula(circuit)
    return formula

# define the function for converting a formula into a graph using the 3-SAT reduction
def three_sat_reduction(formula):
    # convert the given formula into a graph
    graph = convert_to_graph(formula)
    return graph

# define the function for using a Hamiltonian Path oracle to determine whether a graph has a Hamiltonian path
def hamiltonian_path_oracle(graph):
    # use the Hamiltonian Path oracle to determine whether the given graph has a Hamiltonian path
    result = oracle(graph)
    return result

# define the function for creating a non-deterministic Turing machine
def create_turing_machine(n, k):
    # create the Turing machine using the values of n and k and return the result
    machine = TuringMachine(n, k)
    return machine

# define the function for finding the answer to the question of whether n has a non-trivial factor less than k
def has_nontrivial_factor(n, k):
    # create a non-deterministic Turing machine that accepts if there exists a factor of n less than k
    # and rejects otherwise
    turing_machine = create_turing_machine(n, k)

    # use the Cook/Levin reduction to construct a boolean circuit that is satisfiable iff
    # the Turing machine accepts (n, k)
    circuit = cook_levin_reduction(turing_machine)

    # use the Circuit-SAT reduction to convert the boolean circuit into a formula
    formula = circuit_sat_reduction(circuit)

    # use the 3-SAT reduction to convert the formula into a graph
    graph = three_sat_reduction(formula)

    # use the Hamiltonian Path oracle to determine whether the graph has a Hamiltonian path
    result = hamiltonian_path_oracle(graph)

    # since reductions are answer-preserving, the result given by the Hamiltonian Path oracle
    # is the same as the answer to the question of whether n has a non-trivial factor less than k
    return result

# define the main function that will be called to find the answer to the question of whether n has a non-trivial factor less than k
def main():
    # prompt the user for the values of n and k
    n = input("Enter the value of n: ")
    k = input("Enter the value of k: ")

    # find the answer to the question of whether n has a non-trivial factor less than k
    result = has_nontrivial_factor(n, k)

    # print the result to the user
    print("The answer to the question is:", result)

# call the main function to find the answer to the question of whether n has a non-trivial factor less than k
main()
```
Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ So after all of this you will have discovered that "does $n$ have a factor smaller than $k$?" is in NP. But we can just directly show this fact, by observing that testing whether one integer divides another can be done in polynomial time. So what's the point of it all? $\endgroup$
    – Andrej Bauer
    Dec 11, 2022 at 20:08
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Dec 12, 2022 at 0:38
  • $\begingroup$ We're trying to build up a high-quality archive of knowledge that will be useful to others in the future. It seems unlikely that anyone else in the future will have exactly this same question about this same reduction. $\endgroup$
    – D.W. ♦
    Dec 12, 2022 at 0:39
  • $\begingroup$ The purpose was that for awhile I have been a little puzzled that a problem like the prime factorization problem is "the same" as something like the traveling salesman problem. In my first CS class this concept was introduced to me and as I hope you can imagine it seemed a bit odd to me. So after studying a little bit more(I am still an undergrad) I decided to take a crack at actually trying to implement some reduction algorithm between the two. However, from the negative responses I see here I can tell I committed some type of crime so I apologize for offending everyone. $\endgroup$
    – LargeHorse
    Dec 12, 2022 at 2:14
  • $\begingroup$ @LargeHorse, I don't think you've committed a crime. But checking the details of the lengthy argument you've posted takes some time, and everyone here is a volunteer, so it helps to understand the motivation for asking. $\endgroup$
    – D.W. ♦
    Dec 12, 2022 at 4:22

1 Answer 1

Reset to default
3
$\begingroup$

Yes, your reduction looks correct, as far as I can see. I only skimmed it and didn't check every detail carefully.

A computer scientist would probably give a shorter proof that such a reduction exists. First, they would show that the factoring problem is in NP: specifically, to test whether $n$ has a factor less than $k$, a simple witness/certificate for "yes" instances is to output that factor. Then, they would note that the Hamiltonian path problem is known to be NP-complete. Finally, they would note that the definition of NP-complete implies that there is a reduction from any problem in NP to Hamiltonian path, and thus from factoring to Hamiltonian path.

Notice how the computer scientist relies on theorems/facts that have been previously proven by others and are widely accepted, without having to re-iterate the details of those proofs. This provides a form of "abstraction" (in the same way that calling library functions, or decomposing your program into subroutines that you call, makes your code easier to understand) and makes the proof much easier for others to check.

Now, if you want to find an explicit reduction, you could expand the proof of each of those statements above, and you'd obtain such a proof. For instance, you'd find that a standard proof of NP-completeness for Hamiltonian path combines a proof of NP-completeness for SAT (using the Cook-Levin theorem) together with a reduction from SAT to Hamiltonian path. Expanding all of that out leads to exactly the construction you described in your post. This is kind of a tedious exercise that is straightforward to do once you understand the concepts and proofs but is tedious and lengthy to describe in full, so computer scientists normally wouldn't type it all out and instead rely on others to be able to carry out that exercise. It's good that you were able to do it, and it looks like you did it well. This is a good test of your understanding, and it looks like you do understand the subject well.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your response and feedback D.W! $\endgroup$
    – LargeHorse
    Dec 12, 2022 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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