Then I guess if circuit pieces cannot be used to transmit the “signal”, then what are clauses that, I assume, connect verticies in the gadget?
The reason I thought to use AND’s, OR’s was that they are mentioned in the diagram with the V between a1 and a_bar. By the way, what is the purpose of that diamond in figure 5.3?
From what I saw in the book ANDs, ORs and NOTs are used, in figure 8.4 in the book on page 467. Seeing that a clause is only some inputs with some AND’s, OR’s, and NOT’s modifing on those inputs, I assume a set of variables (inputs) with some circles representing operations on some of those inputs is a gadget itself. It has only 1 output. The problem is constructing a circuit that is planar.
To generalize the reduction proof from an known NPC problem P1 to a target problem P2, is it correct to show that an arbitrary instance of P1 can be easily solved by solving P2 polynomial-order times rather than once?
Entries
November 17th, 2008 at 5:40 pm
For 5.1.2, can we assume that the path the problem is talking about is a path with no cycles?
November 18th, 2008 at 3:15 pm
For problem 4 what circuit gadgets can we use: AND, OR, XOR, NOT…?
November 18th, 2008 at 3:28 pm
Usually a path does not have cycles. If it does, and the cycles don’t overlap edges, this is called a walk.
I’m not sure why you need circuit gadgets in problem 4: the goal is to reduce 3SAT to planar 3SAT. there are no circuit gadgets in either problem
November 19th, 2008 at 9:12 am
Then I guess if circuit pieces cannot be used to transmit the “signal”, then what are clauses that, I assume, connect verticies in the gadget?
The reason I thought to use AND’s, OR’s was that they are mentioned in the diagram with the V between a1 and a_bar. By the way, what is the purpose of that diamond in figure 5.3?
November 19th, 2008 at 11:19 am
well you have to use clauses as gadgets since you have to convert 3SAT to Planar 3SAT. The trick is finding the right clauses to use
November 19th, 2008 at 6:17 pm
From what I saw in the book ANDs, ORs and NOTs are used, in figure 8.4 in the book on page 467. Seeing that a clause is only some inputs with some AND’s, OR’s, and NOT’s modifing on those inputs, I assume a set of variables (inputs) with some circles representing operations on some of those inputs is a gadget itself. It has only 1 output. The problem is constructing a circuit that is planar.
November 23rd, 2008 at 10:19 pm
Is the graph G in an instance of LONGESTPATH a directed graph?
November 23rd, 2008 at 10:23 pm
Not necessarily.
November 23rd, 2008 at 10:27 pm
Are we allowed to use a directed version for the reduction part of the NPC proof?
November 23rd, 2008 at 10:28 pm
You have to use the graph as specified. G (as stated) is undirected.
November 24th, 2008 at 7:17 pm
To generalize the reduction proof from an known NPC problem P1 to a target problem P2, is it correct to show that an arbitrary instance of P1 can be easily solved by solving P2 polynomial-order times rather than once?
November 24th, 2008 at 8:01 pm
In general yes