Peter, (01)
Thanks for forwarding the note about errors in the claimed proof
by Deolalikar. As I said in my earlier note, the reviewers had
suspected that some holes existed, but they weren't sure where. (02)
In any case, all the reviewers (including Neil Immerman, who
discovered the flaws in Deolalikar's proof) noted that it was
a respectable effort that was based on a thorough review of
the literature on the subject. (03)
The implications that I drew (copied below) were based on
the literature that Deolalikar had referenced and summarized.
None of them are affected by the parts that were erroneous. (04)
In the following, I mark my previous comments by JFS, Deolalikar's
statements by VD, and leave my new comments unmarked. (05)
John
_______________________________________________________________ (06)
JFS> I share some of the concerns mentioned in these blogs. But whether
> or not there are flaws in Deolalikar's paper, he makes points that
> are valuable in themselves, independently of their use in the proof.
>
> As that discussion shows, the complexity class for many kinds
> of problems can be determined by checking the problem statement.
> If a problem is in an easy class, solve it quickly. But if it's
> in the NP-hard class, warn the user and don't attempt to solve it,
> unless the user insists. (07)
VD> While a given CSP [constraint satisfaction problem] ... might
> be NP-complete, many instances of the CSP might be quite easy to
> solve, even using fairly simple algorithms. Furthermore, such
> 'easy' instances lay in certain well defined regimes of the CSP,
> while 'harder' instances lay in clearly separated regimes. (08)
Previously established material shows how to design tests for
many kinds of problems. That point is not affected by any errors
in VD's poof. However, VD will have to go back to the drawing
board to reformulate his claimed proof to cover all possible cases. (09)
VD> The central concern of this work has been to understand what are
> the irreducible interactions between the variables in a system --
> namely, those that cannot be expressed in terms of interactions
> between smaller sets of variables with conditional independencies
> between them. (010)
The main value of the paper is that VD summarizes and clarifies
many of those connections that had previously been scattered in
a wide range of publications. (011)
VD> This explains why polynomial time algorithms fail when interactions
> between variables are O(n) at a time, without the possibility of
> factoring into smaller pieces through conditional independencies. (012)
JFS> In other words, hard problems have long-distance interactions among
> most of the variables. The symbol O(n) means that most variables
> interact with some significant percentage of the other n variables,
> including many that are in remote regions of the problem statement. (013)
VD> This also puts on rigorous ground the empirical observation that
> even NP-complete problems are easy in large regimes, and become
> hard only when the densities of constraints increase above a
> certain threshold." (014)
JFS> By "empirical observation", he means what most programmers and
> knowledge engineers know: large numbers of such problems are
> easy to solve, and they only become hard when the density of
> long-distance interconnections becomes high. (015)
VD> This threshold is precisely the value where O(n) interactions
> first appear in almost all randomly constructed instances." (016)
JFS> That is the criterion for distinguishing easy problems from
> hard problems. (017)
VD> The framework we have constructed allows us to analyze the set
> of polynomial time algorithms simultaneously, since they can all
> be captured by some LFP [least-fixed-point method], instead of
> dealing with each individual algorithm separately. It makes
> precise the notion that polynomial time algorithms can take
> into account only interactions between variables that grow
> as poly(log n), not as O(n). (018)
As Neil Immerman pointed out, VD made some erroneous assumptions
about the LFP issues. That doesn't invalidate the following: (019)
JFS> In other words, the easy problems are ones for which the number
> of interactions among variables grows very slowly (log n) as the
> the number n of variables increases.
>
> For hard problems, each variable is connected to a significant
> fraction O(n) of all other variables. Such problems are also
> characterized by a high density of variables in each Boolean
> assertion: i.e., each assertion contains O(n) variables.
>
> In terms of graph isomorphism, there is a clear criterion for
> easy problems: Easy graphs are those for which an upper bound on
> the number of links to any node is determined by some polynomial
> in (log n). For typical conceptual graphs and RDF graphs on the
> WWW, this kind of upper bound is almost always true. That means
> graph matching can be done in polynomial time. (020)
VD> polynomial time algorithms succeed by successively 'breaking up'
> the problem into smaller subproblems that are joined to each
> other through conditional independence. (021)
This is a nice way to summarize previously known results. (022)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (023)
|