Re: Exponential Problems and Exponential Computers

[z007400b@bcfreenet.seflin.lib.fl.us (Ralph Silverman)]

Antti J. Ylikoski (ylikoski@cc.hut.fi) wrote:

: Recently, there was an entry in the comp.ai which concerned problems
: which have an exponential complexity, and computers whose capacity
: seems to grow exponentially with time.

: First, "exponential" problems.  There are two kinds of "exponential"
: problems: nondeterministic polynomial-time problems, and tree search
: problems.  I have posted an entry in the comp.ai entitled "The set
: NP-P is nonempty", in which I showed that these problems are closely
: related.  A problem in NP can be represented with a tree search; and a
: tree search problem can be solved by a nondeterministic Turing machine
: in polynomial time.

: Let the tree have a branching factor B, and let the problem be such
: that the depth of the tree to be examined is D.  D corresponds
: approximately to the difficulty of the problem, or, the skill of the
: program.  Then, the time required to examine the entire tree is:

: (1)	T = A * (B^D) / M

: where
: 	T = the real time;
: 	A is a constant;
: 	M = the speed of the computer in MIPS.

: Next, "exponential" computers.  The speed of the state-of-the-art
: computers is:

: (2)	M = C * e^(F*Y)

: where
: 	M = the speed of the computer in MIPS;
: 	C is a constant;
: 	e = 2.7182818;
: 	F is a constant;
: 	Y = the year, with year 0 being Anno Domini 1900.

: Combining (1) and (2) we have:

: (3)	T = A * (B^D) / [C * e^(F*Y)]
: 	  = K * (B^D) / [e^(F*Y)]

: where

: 	K is a constant.

: In practise, T is a constant; typically, T = 24 hours.  Now, we can
: see that even the second most difficult problems we know --- the
: exponential problems --- have the property that with many good people
: working on the problems, the skill of the AI programs grows well with
: time.

: (I said the second most difficult problems ... the most interesting
: formal systems are unsolvable.  I would like to note that even with
: unsolvable problems, we have hope ... from the history of science we
: can see that there have been "impossible" problems which have been
: solved by science.  For example, there was a time when smallpox was an
: "impossible" problem, but science has eradicated the smallpox virus
: from the face of the earth.)

: 	Cheers,
: 	Andy Ylikoski
: 	Helsinki University of Technology

--
**********begin r.s. response*************

	it is effectively impossible
	to prove that a 
		problem
		^^^^^^^
	has intractable time complexity...
	only that a 
		solution does!!
		^^^^^^^^

	also...
		approximate solutions...
	that may be plenty good enough!!


**********end r.s. response***************
Ralph Silverman
z007400b@bcfreenet.seflin.lib.fl.us




--

Ralph Silverman
z007400b@bcfreenet.seflin.lib.fl.us