Re: tar to multiple files

From: Ed Murphy (emurphy42_at_socal.rr.com)
Date: 09/10/03 

Date: Wed, 10 Sep 2003 16:36:55 GMT

On Wed, 10 Sep 2003 13:29:36 +0100, Andy Baxter wrote:

> Peter T. Breuer wrote:

>> OK. Well, you'll have to solve the bin-packing problem then. Sorry, but
>> it's equivalent to the travelling salesman problem. And that's
>> NP-complete.

> Is NP-completeness where any algorithm for an optimal solution grows very
> fast (according to some definition I can't remember) compared to the number
> of entities involved?

Kinda sorta.

NP is the set of problems that can be solved by a deterministic algorithm
that takes polynomial time, compared to the number of inputs.

P is the set of problems for which a potential solution can be checked by
a deterministic algorithm that takes polynomial time.

NPC is the set of problems in NP (X) such that any other problem in NP (Y)
can be reduced to X (i.e. an algorithm to solve X leads to an algorithm to
solve Y) in polynomial time.

Any problem in NPC (and thus any problem in NP) can be solved by a
deterministic algorithm that runs in *exponential* time: simply
generate and test every possible solution. However, compared to *any*
polynomial time (no matter how awful), exponential time - given
sufficiently many inputs - is even worse.

One of the Big Questions in mathematics is: "Does any problem in
NPC (and thus every problem in NP) belong to P?" Most mathematicians
believe the answer is no.

This will give you lots more detail:

http://www.wikipedia.org/wiki/Complexity_classes_P_and_NP

Relevant Pages

  • Re: about CNF converting
    ... deterministic algorithm in order to convert ... an equivalent CNF formula? ... a nondeterministic algorithm that runs in polynomial time would have ... to somehow get to the full formula in polynomial time, ...
    (comp.theory)
  • {{Millennium Problems}}
    ... verified in polynomial time, so this problem is in '''NP'''. ... single fast algorithm for any of them is known. ... complexity for instances with 50–10,000 variables is ... {{quote|...it would transform mathematics by allowing a computer to ...
    (sci.math)
  • Re: Ultimate check, new way to factor or not?
    ... > polynomial time. ... Now, factoring is in general hard, with *certain* types of numbers, ... the mathematics or what's possible, but only in trying to dismiss my ... while certain key features of my discovery make it very exciting, ...
    (sci.crypt)
  • Re: NP-Completeness (from Computers and Intractability)
    ... he says is partly contradictory and wrong. ... IMHO the whole thing is about defining a *complexity* ... can be *solved* by polynomial time nondeterministic ... In mathematics we are bound to consistency at least. ...
    (comp.theory)
  • Re: Factoring problem, solved
    ... rather moer about you seeming pathetically simple. ... Where did you prove anything about polynomial time? ... What do you mean by "j gets background factored by the mathematics"? ... I thought it was a composite. ...
    (sci.crypt)