Re: NP-Complete Definition

On Apr 29, 10:28 pm, bobbysoa...@xxxxxxxxx wrote:
My "Introduction to the theory of computation" book by Michael Sipser
has this Theorem regarding NP-Completeness:

If B is NP-Complete and B is polynomial-time-reducible to C (where C
is in NP), then C is NP-Complete.

This makes sense to me, but the following scenario is confusing.
Suppose that the reduction R reduces B to C in polynomial time, but
that the input to C obtained after applying the reduction is of a
different size than the original input to B.

Sure, that can happen and often does.

Maybe the original input to B was of size n, and after applying the
reduction we are left to solve C with an input of size 2^n.

That could be a possible (general) reduction, but...

The reduction occurs in polynomial time.

No, that cannot happen at all if it is to be a polytime reduction. A
reduction of one problem A to another B is really a way of solving A
using B as a black box. So no 'self-extracting expanding-exponentally'
inputs; you do all the work before handing over to B. And if this is
to be done in polytime, you certainly can't hand over something of
exponential size because just writing that out, forget the time to
compute it, would take at least exponential time (at least 1 unit of
time per bit written out (as Time said)).

So a polytime reduction can't (by definition) result in a exponential
size input to the 2nd problem.

Mitch

.

Relevant Pages

  • NP-Complete Definition
    ... If B is NP-Complete and B is polynomial-time-reducible to C (where C ... Suppose that the reduction R reduces B to C in polynomial time, ... Maybe the original input to B was of size n, ... The reduction occurs in polynomial time, ...
    (comp.theory)
  • Re: Reductions in P
    ... P-completeness is to show that a ploblem may be intrinsically ... P1 in P, P2 in NP-complete. ... I'd say that it is possible, since reduction can be read as ...
    (comp.theory)
  • Re: dumb question: why is it called a "reduction"?
    ... Tell a mathematician that he's faced with a house on fire, ... How does he put out the fire? ... The idea of a reduction is that by performing the reduction, ... the difficulty of B. Solving A can't be any harder than solving B, ...
    (sci.crypt)
  • Re: A newbie question regarding P
    ... > using a polytime reduction. ... write over the whole input - the other is the working tape, ... for a LOG-SPACE reduction our Turing Machine, ...
    (comp.theory)
  • Re: An easy one!
    ... LINEAR < P. Look up the "time hierarchy theorem." ... means that if I'm solving it in poly-time it's already about as fast as ... it depends on how the reduction works. ...
    (comp.theory)