It's just that "problem X is NP-hard" means roughly "Any problem Y in NP is polynomial-time reducible to problem X", and your example did not seem to exemplify this...
All your example seemed to exemplify was a problem that was solvable in polynomial time (class P, not class NP-hard) However, this is irrelevant to your main conceptual point, which as I understood it was that theorems regarding the scaling behavior of the worst-case complexity of problems as problem size n goes to infinity are pragmatically irrelevant... [I'm not sure I fully agree with your conceptual point, but that's another issue. I used to agree but when I encountered Immerman's descriptive complexity theory, I started wavering. Immerman showed e.g. that -- P, the class of problems solvable in polynomial time, corresponds to languages recognizable by first-order logic plus a recursion operator -- NP, the class of problems whose solutions are checkable in polynomial time, corresponds to languages recognized by existential second order logic (second order logic with second-order existential but not universal quantification) This is interesting and suggests that these complexity classes could possibly have some fundamental cognitive meaning, even though such a meaning is not obvious from their standard definitions...] -- Ben On 11/24/06, Richard Loosemore <[EMAIL PROTECTED]> wrote:
Ben Goertzel wrote: > Richard, > > I know it's peripheral to your main argument, but in this example ... > >> Suppose that the computational effort that evolution needs to build >> "different sized" language understanding mechanisms scales as: >> >> 2.5 * (N/7 + 1)^^6 planet-years >> >> ... where "different sized" is captured by the value N, which is the >> number of conceptual primitives used in the language understanding >> mechanism, and a "planet-year" is one planet worth of human DNA randomly >> working on the problem for one year. (I am plucking this out of the >> air, of course, but that doesn't matter.) >> >> Here are the resource requirements for this polynomial resource function: >> >> N R >> >> 1 2.23E+000 >> 7 6.40E+001 >> 10 2.05E+002 >> 50 2.92E+005 >> 100 1.28E+007 >> 300 7.12E+009 >> >> (N = Number of conceptual primitives) >> (R = resource requirement in planet-years) >> >> I am assuming that the appropriate measure of size of problem is number >> of conceptual primitives that are involved in the language understanding >> mechanism (a measure picked at random, and as far as I can see, as >> likely a measure as any, but if you think something else should be the >> N, be my guest). >> >> If there were 300 conceptual primitives in the human LUM, resource >> requirement would be 7 billion planet-years. That would be bad. >> >> But if there are only 7 conceptual primitives, it would take 64 years. >> Pathetically small and of no consequence. >> >> The function is polynomial, so in a sense you could say this is an >> NP-hard problem. > > I don't think you're using the term "NP-hard" correctly. > > http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP > > " > The class P consists of all those decision problems that can be solved > on a deterministic sequential machine in an amount of time that is > polynomial in the size of the input; the class NP consists of all > those decision problems whose positive solutions can be **verified** > in polynomial time given the right information. > " > > [This page also reviews, and agrees with, many of your complaints > regarding the intuitive interpretation of P as easy and NP as hard] > > http://en.wikipedia.org/wiki/NP-hard > > " > In computational complexity theory, NP-hard (Non-deterministic > Polynomial-time hard) refers to the class of decision problems H such > that for every decision problem L in NP there exists a polynomial-time > many-one reduction to H, written . If H itself is in NP, then H is > called NP-complete. > " I'd certainly welcome clarification, and I may have gotten this wrong... but I'm not quite sure where you are directing my attention here. Are you targeting the fact that NP-Hard is defined with respect to decision problems, or to the reduction aspect? My understanding of NP-hard is that it does strictly only apply to decision problems ... but what I was doing was trying to interpret the loose sense in which Eric himself was using NP-Hard, so if I have stretched the definition a little, I woudl claim I was inheriting something that was already stretched. But maybe that was not what you meant. I stand ready to be corrected, if it turns out I have goofed. Richard Loosemore. ----- This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?list_id=303
----- This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?list_id=303
