Algorithm classes

Question 1

SAT language

Answer 1

}לפסוק Φ בצורת CNF קיימת השמה מספקת SAT={Φ|

Question 2

Algorithm to solve SAT given algorithm to decide SAT A

Answer 2

For every Xi in the cnf, declare it as true and check if A still returns true. If so than it is True, if not than false.

Question 3

The P class

Answer 3

A language L can be decided using an algorithm A in polynomial time.

Question 4

The NP class

Answer 4

You can validate if there is a solution to the problem with an algorithm a and the original input alongside some additional input (usually the solution) in polynomial time.

Question 5

Hamilton circuit problem

Answer 5

Given a graph and a set of edges we can validate in polynomial time if there is a Hamilton cycle or not (by checking if the edges go through all the nodes once)

Question 6

Traveling salesman problem

Answer 6

Given a graph, a path in it and a target cost k, We can check if the input is a solution that does not exceed 10.

Question 7

Partition problem

Answer 7

Given a group of numbers, find a partition of the group into two so that the new groups sums are equal.
Given a group and a possible partition it is easy to validate the solution by just checking if it is correct.

Question 8

Given an algorithm A which decides the partition problem, create an algorithm to find the partition

Answer 8

Start by adding any two items, x, y in the group into one. Now you have a smaller group, run A on it. If it returns true, then you know that x and y are In the same group. Else, they are separate. Do this until you are left with two items in the group.

Question 9

Knapsack problem

Answer 9

Given a backpack with volume v, put in it the items which add up to the biggest value.
Given a backpack’s volume, a group of item and a target price of k, we can easily check that all is valid.

Question 10

Integer Linear Programming

Answer 10

Given a set of constraints that are translated into a set of equations, solve the equations so that the solutions are integers. To the non integer problem there is a solution using the simplex algorithm in a “ok” time. A solution is easily validated that it doesn’t exceed a value k by just assigning the solution in the equations.

Question 11

Perfect number problem

Answer 11

A perfect number is a number that is equal to the sum of all its dividers which are smaller than it.
In order to validate if number is perfect or not, you can take use of the decomposition into prime numbers. Then take use of a formula to calculate the sum of the decomposition S and see if S=2n (n is the tested number).
S = (1+P1+P1^2 +….P1^K1)…. (1+Pm+Pm^2 +….Pm^Km)

Question 12

co-NP

Answer 12

{L | L~ ∈ NP}
P ⊆ NP
P ⊆ co-NP

Question 13

P or NP: 2 color graph

Answer 13

P: given a graph it is easy to say if it is colorable or not, by just running a simulation and seeing if their is a contradiction.

Question 14

P or NP: 3 color graph

Answer 14

NP and even NPC

Question 15

P or NP: 2 SAT

Answer 15

P: given a CNF equation, just check