Ben Goertzel wrote:
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...]
Your point is well taken: I did fudge the issue by giving an example
that was a specific, polynomial instance and made the mistake of calling
it NP-Hard. My goal (as you correctly point out) was to try to make it
clear that NP-Hardness statements are not about how hard a given
language mechanism is to build, but about the scaling behavior.
I don't really want to get too sidetracked, but even if Immerman's
analysis were correct, would this make a difference to the way that Eric
was using NP-Hard, though? In other words, this would still not
undermine my point that a statement like "the building of a language
/learning mechanism by evolution is NP-Hard" does not actually tell us
anything about how difficult the particular process that led to human
language really was? It sounds like Immerman is putting the
significance of complexity classes on firmer ground, but not changing
the nature of what they are saying.
Richard Loosemore
-- 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
-----
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
