NP-Complete Definition

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.
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.
The reduction occurs in polynomial time, so by Sipser's definition C
would be NP-Complete, but we did transform the input size
significantly, so i don't know if C would really be NP-Complete.
If C is NP-Complete based on this reduction alone, then a polynomial
time algorithm for C would not imply P = NP, like Sipser says in the
following page.
If C cannot be considered NP-Complete because it changed the size of
the input to a different order, then shouldn't that be a constraint of
the initial definiton i quoted at the top of this post?

Or maybe it's impossible that R, running in polynomial time, may be
able to exponentially increase the original input size. The example i
had in mind is where B receives n bits. The reduction R from B to C
builds a program that can return the i'th subset of k bits (from the
original n bits), where k is variable, for example. There would be
something like n^k such subsets. Suppose then that these subsets are
used as input to C.
The reduction can't pass all subsets to C in polynomial time, because
there's too many subsets, but it can pass to C something which is able
to access each of the subsets, which is just as good as far as C is
concerned.
So B is reduced to C in polynomial time, but the input size changed
substantially. Would we classify C as NP Complete based on this?

.

Relevant Pages

  • Re: 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, ... that cannot happen at all if it is to be a polytime reduction. ... reduction of one problem A to another B is really a way of solving A ...
    (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: Consecutive Numbers
    ... NP problem is said to be NP-complete if the>existence of a polynomial ... footing--- if any one of them can be solved in polynomial time, ... to be non-P or NP>"Finding the prime factors of a given integer is ... it does, then factorization, which is certainly in NP ...
    (sci.math)
  • Re: NP-complete and NP-Hard?
    ... > I don't quite understand NP-Complete and NP-Hard problem, ... NP is the class of problems that can be solved in polynomial time (in ... that you need exponential time to solve an NP problem - there might be ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... Radoslaw Hofman wrote: ... If there is a UP set that is NP-complete, ... he may solve any TSP instance in polynomial time then he can solve any ... (unique solution and polynomially solvable) ...
    (comp.theory)
Loading