[Polynomial-time reduction] Consider the construction of a graph (a.k.a. “gadget

Question

[Polynomial-time reduction] Consider the construction of a graph (a.k.a. “gadget”)
studied in class when proving the polynomial-time reducibility 3-SAT ?p INDEPENDENT-SET.
The construction steps are shown below.
1. Add 3 vertices for each clause, one vertex for each literal.
2. Connect the 3 vertices in each triangle.
3. Connect the vertex of a literal and its negation between triangles.
Show that this construction take polynomial time. Assume a 3-SAT formula ? is given as a text
string that is linearly parsed into literals and clauses. It is adequate to give an informal but
accurate analysis of the construction running time complexity in big-O. If you will, however, feel
free to actually write the construction algorithm in pseudocode to analyze the running time
complexity.

Explanation / Answer

Point is not that n2000 is a nice time bound, or that the differences among n and 2n and n2 are negligible. Rather, simple theoretical tools may not easily capture such differences, whereas exponentials are qualitatively different from polynomials and may be amenable to theoretical analysis. “My problem is in P” is a starting point for a more detailed analysis “My problem is not in P” may suggest that you need to shift to a more tractable variant

Next year's computer will be 2x faster. If I can solve problem of size n0 today, how large a problem can I solve in the same time next year?

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.