Date: 14 Apr 1995 23:35:15 GMT
From: phuegler@epix.net (Peter A Huegler)
Subject: Unary and Binary NP-hard
Can anyone give me a description of the differences between unary NP-hard
and binary NP-hard? Thanks in advance.
Pete Huegler
Date: 23 Aug 1995 17:08:14 GMT
From: naylor@mti.sgi.com (William Clark Naylor)
Subject: P!=NP does NOT imply NPC cannot be solved
It seems to me that people discussing NP-completeness have been overlooking something very obvious and I would like to state it here as a reminder.
As an engineer, I am interested in solving NP-complete problems quickly by computer because this would give me the ability to solve many economically important problems that I cannot now solve. If somebody can find a practical computer algorithm for solving some NP-complete problem, I can write a compiler/translator from any other NP-complete problem and use the algorithm as a subroutine to solve the problem. The P-time algorithm could be used to solve a huge variety of problems, much as the simplex method is used to solve a huge variety of problems today.
The simplex algorithm is a practical algorithm, but it is NOT a polynomial time algorithm in the formal sense used in NP-completeness theory. The simplex method seems to run in polynomial time for almost all problems and for all problems of practical interest. But for a small class of problems simplex has been shown to require exponential time (the Klee-Minty examples). Speaking as a mathematician: these examples are cute. Speaking as an engineer: I don't care at all.
A proof that P != NP would not rule out the existence of a procedure for solving NP-complete problems with properties similar to simplex method. The existence of such a procedure would solve the practical problem that motivated the development of NP-completeness theory without proving either P = NP or P = co-NP.
Date: 23 Aug 1995 23:09:27 -0400
From: cbbrown@io.org (Christopher B. Browne)
Subject: P!=NP does NOT imply NPC cannot be solved
If P=NP, then this *might* mean that you could solve NP-complete problems quickly.
With the assumption that the polynomial was of reasonably low degree.
That's a fairly critical assumption.
If we proved that NP=P, for some P algorithm with performance time of order O(n^256), solving problems of size greater than 1 would be fairly much unreasonable.
In many cases, algorithms that are of polynomial complexity have been shown to have fairly *low* polynomial complexity. I haven't seen any algorithms lately that are of degree higher than about 4 or 5.
Christopher Browne - Email:<cbbrown@io.org>,
WWW:<http://www.io.org/~cbbrown/>
Q: How do you make Windows go faster??? A: THROW IT HARDER!!!
Date: 24 Aug 1995 11:39:15 GMT
From: nmm1@cus.cam.ac.uk (Nick Maclaren)
Subject: P!=NP does NOT imply NPC cannot be solved
In article <41fn9u$121@chronicle.mti.sgi.com>, naylor@mti.sgi.com (William Clark Naylor) writes .....:
Your first sentence is correct, but your second is incorrect. It is quite possible that the appropriate mapping from a particular NP complete problem to the general solution procedure would map some of the practical cases onto the intractable 'special cases'. Such a general procedure MIGHT help, but there is no guarantee that it would.
I agree with you that the standard P = NP question is of theoretical interest only, but the problem is that the related practical questions are extremely difficult to handle mathematically.
Nick Maclaren,
Dan
Date: Thu, 24 Aug 1995 15:09:36 GMT
|
I think this is an excellent point, but there is one thing you have to
be careful about. There are many NP-complete problems which seem
relatively tractable "on average," and others which are very difficult
"on average." Unfortunately, when you try to reduce one to the other,
you generally end up blowing up the size of the problem and getting a
non-average instance of it, making the resulting problem just as hard
to solve as the original, so that the relatively easy NP-complete
problems don't help in solving the hard NP-complete problems.
Thus, a good average-case solver for satisfiability may not help at
all in finding chromatic number. The remarkable thing about linear
programming is that ALL the linear programs people come up with in
practice seem to behave well with the simplex method (some much better than others, admittedly, but all behave a lot better than the
worst-case examples).
Peter Shor
Date: Sat, 26 Aug 1995 15:53:00 -0400
On 25 Aug 1995, Ioannis (Yanni) G. Tollis wrote:
>
> Finally, it is not even clear to me whether the question P =? NP
> is the right question.
>
> Yanni Tollis
Sorry for intruding, but what do you mean by "right question" ?
Cheers!
Date: 25 Aug 1995 21:08:06 GMT
mark@omnifest.uwm.edu (Mark Hopkins) wrote:.....
I've been working on Hamiltonian circuits for a few years. (I prefer
Hamiltonian circuits to paths for some reason.) I am only an enthusiasic amateur, but my lack of training could be considered a lack of indoctrination. If current wisdom is insufficient, maybe it is, shall we say, contaminated; or maybe lack of training leaves me free to think from the ground up, whereas if I had too much knowledge, I would have many places to start and pick the wrong one; or I would just plain learn to see things in some way that happens to be limiting. (Or I'm too impatient, but that's my business, I think.)
I presented a scheme, buried amongst other comp.theory posts, that got two interesting responses. One, by private email, ascertained that I "...outline a method to prove that HAMILTONIAN PATH [CIRCUIT] is in co-NP...It would not imply that NP = co-NP."
The other was posted by Matthew Saltzman, in which he asked "But what is it that 'contrarians' should find persuasive? I am arguing that it runs counter to our intuition about the relative difficuly of verifying that a graph is not Hamiltonian versus verifying that it is."
I think my scheme does indeed suggest that NP = co-NP. As to the intuitive part: A non-deterministic algorithm effectively does everything at once, as if it has infinite force, or magic, or something. Because it checks everything (infinite force) or nothing (magic), we can ONLY expect (intuit) that any co-NP certificate it produces is exponential (or null). But notice that a deterministic algorithm is different. Because it's (required to be) efficient, it does not check everything, so its co-NP certificate is not nesessarity exponential.
If some algorithm can efficiently find a circuit, it MUST be testing and
searching efficiently. So, the set of its test operations SHOULD be minimal.
If it can, the algorithm directly certifies a yes-graph, one that is
Hamiltonian. If it has determined that the graph is not Hamiltonian, then the set of test operations is collected and represented as a SAT problem. The SAT problem is poly-transformed into a second (very different) graph. The algorithm should be able to certify that this second graph is Hamiltonian, indicating that "yes, the original graph is not Hamiltonian." Since any NP-complete problem is poly-reducible to any other, any of them can be handled in this way, of course.
If the second graph is proportional (how?) to the first, then NP = co-NP. But aside from that, I would really like to know if this scheme is reasonable, separately from what it may or may not prove. It makes sense to me, but it fits into the broader frame of theory, and I know I'm not equipped to critique it properly.
8/25/95 Jan Braswell <braswell@fly.hiwaay.net>
From: tollis@utdallas.edu (Ioannis (Yanni) G. Tollis)
Yes, good points, BUT a P-time algorithm is not necessarily an efficient
algorithm (at least in practice). Besides, as Peter mentioned with each transformation you will increase the problem size.
Finally, it is not even clear to me whether the question P =? NP is the right question.
Yanni Tollis
Date: 29 Aug 1995 03:30:29 GMT
Amitava
Date: 29 Aug 1995 05:07:42 GMT
In article <41u1kl$e00@grivel.une.edu.au> datta@neumann.une.edu.au (Amitava Datta) writes:
D. J. Bernstein (djb@silverton.berkeley.edu) wrote:
: Counting points on an elliptic curve is currently at degree 6.
Cutting a maximum area convex polygon from an arbitrary simple
polygon (potato peeling problem) is n^9, where n is the number of
vertices of the simple polygon.
By this, are you talking about the lower bound of the
problem, or the best found algorithm??
Fumiaki Kamiya
Date: Tue, 29 Aug 1995 11:27:03 -0400
This should be upper-bound (or as you say the best found algorithm)...
So far as I know there are no polinomial lower bounds other then linear....
(Would be nice if someone showed me one)..
Cheers!
Date: 29 Aug 1995 20:52:38 GMT
In which case, I think it would be premature to say that
there are problems with high degree polynomial just because
that's the best we have done so far.
What I think would be an interesting question is whether
there is a problem with high degree polynomial lower bound.
Fumiaki Kamiya
Date: 30 Aug 1995 09:19:03 GMT
For a generic example, consider the program that determines whether
an arbitrary K-parameter decision function (implemented as an oracle)
ever returns "yes" for values taken from within a set of size N.
This is trivially O(N^K) in all respects for a deterministic, serial
machine. It is neither natural nor interesting.
Nick Maclaren,
Date: Thu, 31 Aug 1995 13:59:29 GMT
> Nick Maclaren
Infinite. Where the complexity of a problem exceedes the ability to compute it, there is an effective infinite complexity, ie. you can continue trying to compute it forever. eg: If each step taken towards a goal is of 0 length, then the goal cannot be reached in less than an infinite number of steps. The computational answer to "Will the walker reach his goal?" is never.
Equivalently: a walker taking 0 steps of any length towards a goal will never reach it.
The only solution, and the solution to both, otherwise intractable problems, is the case that the walkers initial position is also his goal!
Hence, a single "position evaluation" algorithm solves the problem!
This evaluation works on facts known about the parameters of the
problem, and not the problem itself, effectivly changing the size of
the computational universe, basically a form of complex math. The
complexity of computing a solution to a problem is relative to the
computational viewpoint of the problem space within an n-dimensional universe. Note for the record, that some problems still cannot be solved effeciently(NP) since they span an n-dimensional problem space where |n| is size aleph-nul (first order ifinite). I hypothesize: where the order of the problem space |n| is finite, and a solution exists within the problem space, then an n+1 problem space exists, containing a log(n+1) order solution.
If you're talking to complexity theorists, you probably want to
consider multiple-tape Turing Machines. This is the model in which
classes like P and NP are naturally defined. In this model, as you
say, there are no known superlinear polynomial lower bounds. In fact,
I think the biggest lower bound known is something incredibly small,
like $3n+O(1)$.
If you're talking to computational geometers, you may want to consider algebraic decision trees instead. In this model, most problems that have polynomial-time solutions have lower bounds of $\Omega(n\log n)$.
Some NP-complete problems have lower bounds of $\Omega(n^2)$. Nothing bigger is known.
There ARE a few superlinear lower bounds in more specialized models of computation, in which only a small fixed collection of primitives is
allowed. For example, deciding whether an n-vertex graph is connected requires $\Omega(n^2)$ time, if the only question you're allowed to ask is "are these two vertices connected by an edge?"
Fumiaki Kamiya (kamiya@cse.ucsc.edu) replies:
| What I think would be an interesting question is whether
| there is a problem with high degree polynomial lower bound.
You betcha! There is no hope of separating P from NP until such a
problem is found! (P!=NP implies such a lower bound for any
NP-complete problem.)
Let me propose what I think is a good candidate for such a problem.
There is a class of problems defined by Gajentaan and Overmars, all of
which appear to have quadratic complexity. All such problems can be
quickly reduced to the following simple problem, which they call 3SUM:
Given a set of n integers, do any three sum to zero?
Because of these reductions, they call the problems "3SUM-hard". A
subquadratic algorithm for a 3SUM-hard problem would imply a
subquadratic algorithm for 3SUM. Conversely, a quadratic lower bound for 3SUM (in a sufficiently general model of computation) would imply a quadratic lower bound for every 3SUM-hard problem.
They (and I) conjecture that the complexity of 3SUM really is
$\Theta(n^2)$. There's an easy $O(n^2)$-time algorithm (left to the
reader as an exercise), and an $\Omega(n\log n)$ lower bound is not
too hard, either. There is even an $\Omega(n^2)$ lower bound in a
restricted model of computation.
Jeff Erickson
From: desj@ccr-p.ida.org (David desJardins)
Obviously in a relativized model of computation it is easy to construct
decision problems with any particular lower bound, just by counting the number of necessary calls to the oracle. This seems to have nothing to do with the stated problem though.
Date: 5 Feb 1996 11:07:57 GMT
Is this problem NP-complete?
Can anybody help me in finding a transformation of an NP-complete problem in this problem, if exists.
Thank You.
Maurizio
Date: 25 Mar 1996 17:14:14 GMT
Was wondering if the multicommodity integral network flow problem on a bipartite network is NP complete?
Any references/pointers to this will be appreciated.
Thanks.
Gautham.
Date: 7 Jul 1996 23:52:17 GMT
A counterexample to my statement above would prove NP==co-NP because it would lead to a polynomial-length optimality proof for your problem.
Date: Thu, 15 Aug 1996 19:04:09 GMT
Date: 5 Sep 1996 15:33:06 GMT
Any answer, comment greately welcome.
Nicola
nick@bau.cba.uh.edu
Date: 5 Sep 1996 12:49:42 -0400
In combinatorial optimization, we talk about a lot of problems in
terms of a graph G = (V,E). In these cases, (roughly speaking) the
input is in terms of the vertices and edges of the graph. So a
polynomial algorithm would be polynomial in terms of the number of
vertices, |V|, and the number of edges, |E|.
Now, a related question is: what is the boundary between P and
NP-complete? (I say "NP-complete" since P is a subset of NP.
However, P and NP are disjoint unless someone proves that P = NP or P
!= NP). This is one of my favorite questions in computational
complexity. Some easy problems become NP-complete with some small
modifications. For instance, minimum spanning tree is easy, but
Steiner tree is NP-complete. Shortest path is easy, but longest path
is NP-complete. Undirected Chinese Postman is easy, but travelling
salesman is hard. If you can understand how adding (or deleting)
structure changes a problem from easy to hard (or vice-versa), then
you really get an appreciation for computational compexity.
The point is that there are many problems where the problem is in P but
some variant of the problem is in NPC.
By the way, I assume that since P ?= NP is unanswered, it is not known
whether NP-complete is a proper subset of NP. So there may or may not be
"NP-incomplete" problems out there?
-- Paul
Date: 7 Sep 1996 16:46:36 GMT
If I understand correctly, I think there are several cases depending
on how K is determined by the problem input. Suppose input length
is L, and K is a function of L, say, K=F(L). Then
Date: Tue, 17 Dec 1996 15:04:28 -0800
Definition of SS:
Let an instance of Subset Sum (SS) be denoted by SS'. Let any SS' be
given by:
Let c, a positive integer with n bits, denote the certificate. Let
there be a 1 to 1 correspondence between the n bits of c and the n
elements of z. c is used to indicate a selection of the elements of z
by the following rule:
If a bit of c is 1, the corresponding element in z is selected,
otherwise it is not selected.
The elements selected by c are to be added together. Note that there
are 2^n unique certificates and as many unique selections of the
elements of z. Note also that any given certificate c indicates a
particular subset of z.
The decision problem for SS is this:
Does there exist a c, such that its indicated sum equals s?
Definition of SSM:
Let an instance of Subset Sum Mod M (SSM) be specified in the same way
as an instance of Subset Sum, except that the SSM instance also
includes the positive integer M.
The decision problem for SSM is this:
Does there exist a c, such that its indicated sum modulo M equals s?
Theorem: SSM is in NPC.
Proof:
Let SSy denote the set of members of SS that admit one or more
satisfying certificates.
Let SSMy denote the set of members of SSM that admit one or more
satisfying certificates.
Any given SS' can be mapped to an SSM' such that SS' is in SSy if and
only if SSM' is in SSMy. The mapping is done this way:
Without any changes, the z and s of the SS' become the z and s
of the SSM'. The M of the created SSM' is simply 1 plus the sum of
every element in z.
The certificate is the same for both instances. What is accomplished,
by such a mapping, is to create an SSM instance so that the M, of the
created instance, is larger than any sum in z, and thus any given
certificate will indicate a selection whose sum is the same for both SS'
and SSM'.
Clearly, the size (in bits) of the created SSM' is polynomial in the
size (in bits) of the SS'. Clearly, the mapping can be performed in
time polynomial in the size of the SS'.
We have seen that that:
SS is known to be in NPC. In accordance with the definition of
"transforms to", we see that SS transforms to SSM. SSM is in NP,
because any certificate (for any instance of SSM) can be verified in
time polynomial in the size of the instance. Therefore, I have shown
that SSM is in NPC.
Proof complete.
Date: 18 Dec 96 06:36:42 GMT
Every instance of Subset-Sum becomes an instance of
Subset-Sum-Mod-M, simply by setting M=Sum of all inputs.
So SS is a special case of SSM, and since SS is NP-complete,
and SSM is in NP, then SSM is also NP-complete.
David
Crawl back to front page.
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: nmm1@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679
Date: 24 Aug 1995 14:27:55 GMT
From: djb@silverton.berkeley.edu (D. J. Bernstein)
Subject: P!=NP does NOT imply NPC cannot be solved
Christopher B. Browne
From: shor@research.att.com (Peter Shor)
Subject: P!=NP does NOT imply NPC cannot be solved
In article ...William Clark Naylor writes:..........
From: Alex Dekhtyar <dekhtyar@cs.umd.edu>
Subject: P!=NP does NOT imply NPC cannot be solved
...Hi, Yanni!...
Alex Dekhtyar
University of Maryland
Dept. of CS
From: Jan Braswell <braswell@fly.hiwaay.net>
Subject: Two weird things about P=?NP
To: Jesper,Larsson,<Jesper.Larsson@dna.lth.se>
Newsgroups: comp.theory,sci.op-research,comp.ai
Subject: Re: P!=NP does NOT imply NPC cannot be solved
Date: 25 Aug 1995 23:06:38 GMT
Organization: The University of Texas at Dallas, ACC
Lines: 40
Distribution: inet
Message-ID: <41ll1u$cas@news.utdallas.edu>
References: <414fdj$alf@fly.HiWAAY.net>
In article ..... shor@research.att.com (Peter Shor) writes: .....
From: datta@neumann.une.edu.au (Amitava Datta)
Subject: P!=NP does NOT imply NPC cannot be solved
D. J. Bernstein (djb@silverton.berkeley.edu) wrote:
From: kamiya@cse.ucsc.edu (Fumiaki Kamiya)
Subject: P!=NP does NOT imply NPC cannot be solved
Just out of curiosity,
From: Alex Dekhtyar <dekhtyar@cs.umd.edu>
Subject: P!=NP does NOT imply NPC cannot be solved
On 29 Aug 1995, Fumiaki Kamiya wrote:
Alex Dekhtyar!>br>
Dept. of CS U. of Maryland
From: kamiya@cse.ucsc.edu (Fumiaki Kamiya)
Subject: P!=NP does NOT imply NPC cannot be solved
In article <Pine.ULT.3.91.950829112417.1923G-100000@snausage.cs.umd.edu> Alex Dekhtyar <dekhtyar@cs.umd.edu> writes:
From: nmm1@cus.cam.ac.uk (Nick Maclaren)
Subject: P!=NP does NOT imply NPC cannot be solved
Yes, easily. The actual question is whether there is a natural and
important problem with that property.
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: nmm1@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679
From: marcoj@ai.rl.af.mil (James D. Marco)
Subject: P!=NP does NOT imply NPC cannot be solved
In article <422oqi$1sk@tang.ccr-p.ida.org>, desj@ccr-p.ida.org (David
desJardins) wrote:
From: jeffe@ocarina.CS.Berkeley.EDU (Jeff Erickson)
Subject: Superlinear lower bounds
Alex Dekhtyar <dekhtyar@cs.umd.edu> writes:
jeffe@cs.berkeley.edu
http://www.cs.berkeley.edu/~jeffe
Newsgroups: comp.theory,sci.op-research,comp.ai
Subject: Re: P!=NP does NOT imply NPC cannot be solved
Date: 30 Aug 1995 18:30:41 -0400
Organization: IDA Center for Communications Research, Princeton
Lines: 22
Distribution: inet
Message-ID: <422oqi$1sk@tang.ccr-p.ida.org>
References: <414fdj$alf@fly.HiWAAY.net>
<Pine.ULT.3.91.950829112417.1923G-100000@snausage.cs.umd.edu>
<KAMIYA.95Aug29135238@arapaho.cse.ucsc.edu><421ae7$1hp@lyra.csx.cam.ac.uk>
NNTP-Posting-Host: tang.ccr-p.ida.org
Nick Maclaren
From: pietrant@unive.it (Maurizio Pietrantuono)
Subject: NP completeness
A set is composed of some tasks; the tasks tn have a maximum period of time pn in wich they must be performed; that is to say that each task, tn, has to be performed at least every pn days. On each day can be performed no more than one task. We want to minimize the number of working days over a fixed period of time.The fixed period of time is bigger than the biggest pn.
From: ghv@acsu.buffalo.edu (Gautham H. Vemuganti)
Subject: NP Complete ?
Hi!
From: naylor@synopsys.com (William Naylor)
Subject: LP formulation of NP-hard problems
In article .... David G. Mitchell ...wrote:
From: RVICKSON@MANSCI.uwaterloo.ca (Ray Vickson)
Subject: Computational complexity newsgroup?
Does anyone know of a computational comlexity newsgroup (i.e., NP
completeness, etc.)?
From: nick@Bau.seas.ucla.edu (nick)
Subject: O(n^k) is in P if k is large?
If there exists an optimal algorithm to solve a combinatorial
optimization problem that runs in O(N^K), where N and K are the
problem parameters, can one say that the problem is in P, if K is
of size say 10, 20 or 50, and N is of size say 40, 80, 200?
Is there some middle class between P and NP, where this problem
may lay?
From: gt1086c@prism.gatech.edu (Gregory Glockner)
Subject: O(n^k) is in P if k is large?
The hypothetical algorithm that you describe is NOT polynomial since K
depends on the problem. Roughly speaking, a polynomial algorithm is
some algorithm that can find a solution in time O(n^k), where n is a
function of the length of the input and k is some FIXED constant that
does not depend on the input.
From: gt1086c@prism.gatech.edu (Gregory Glockner)
Subject: O(n^k) is in P if k is large?
I would like to correct a typo I made:
From: rubin@msu.edu (Paul A. Rubin)
Subject: O(n^k) is in P if k is large?
In article <50n0b6$adg@acmex.gatech.edu>,
gt1086c@prism.gatech.edu (Gregory Glockner) wrote:
From: zhi-long chen <zhichen@dragon.princeton.edu>
Subject: O(n^k) is in P if k is large?
To: nick@Bau.seas.ucla.edu
From: Richard Hilburger <rh@aracnet.com>
Subject: Help Needed in Proof that Subset Sum Mod M Is NP-complete
I'm not a professional mathematician. I've been trying to prove that
Subset Sum Mod M Is NP-complete. I would be greatful if anyone,
familiar with this type of proof, would comment on the following. Is it
valid or invalid? If invalid, why? ...can it be
fixed?
From: mitchell@cs.toronto.edu (David G. Mitchell)
Subject: Help Needed in Proof that Subset Sum Mod M Is NP-complete
Your proof is fine, making rigorous the following informal proof;