Re: An easy one!

In article <1155678701.344861.324240@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
D. C. <enharmonix@xxxxxxxxx> wrote:
LINEAR < P, or LINEAR <= P?

LINEAR < P. Look up the "time hierarchy theorem."

I have an algorithm that 2-SAT should be able to reduce to (I
haven't actually confirmed reductions work both ways, though), which
means that if I'm solving it in poly-time it's already about as fast as
it's going to get, right?

Not necessarily; it depends on how the reduction works. If the reduction
causes a 2-SAT instance of size n to blow up to an instance of your
problem of size n^3 for example, then potentially your problem can be
solved faster than 2-SAT by a cube root factor.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • 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: 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)