One might consider heuristics like AMAF, pattern knowledge, etc. to be
simply a more effective way to guide exploration. The UCB term has no
domain-specific knowledge. It works surprisingly well but it should be
no surprise that one can do better with domain-specific knowledge.
The problem of
-Original Message-
From: [EMAIL PROTECTED] [mailto:computer-go-
[EMAIL PROTECTED] On Behalf Of Don Dailey
Sent: Monday, August 11, 2008 8:31 PM
To: computer-go
Subject: RE: [computer-go] Re: mogo beats pro!
On Mon, 2008-08-11 at 20:10 -0700, David Fotland wrote
Quoting Don Dailey [EMAIL PROTECTED]:
Yes, UCT is easier to use with multiple CPU's because with additional
processors alpha-beta programs do wasted work, unless you are talking
about theoretical programs with perfect move ordering, which you aren't.
Nice that all is clear about alpha-beta
I don't know the answer, but it wouldn't surprise me if it turned out
that the same theoretical issues exist for most reasonable tree search
schemes. So it is possible that UCT has no superiority over alpha-beta
when it comes to making a parallel program. But I don't really know.
- Don.
On
Not an expert on AB-search or UCT search but there's a subtle
difference I think. In AB search, if some processors have been
searching in a branch that is subsequently cut off, the work is 100%
wasted. In UCT there's no such black-and-white cutting. If you do
sampling in what then turns
Magnus Persson: [EMAIL PROTECTED]:
Quoting Don Dailey [EMAIL PROTECTED]:
Yes, UCT is easier to use with multiple CPU's because with additional
processors alpha-beta programs do wasted work, unless you are talking
about theoretical programs with perfect move ordering, which you aren't.
Nice
this is interesting!
perhaps i misunderstand the setup of the experiment -- what
is the unit of measure for the delay, or how is delay being
implemented?
the FIFO queue is doing what, and where is the delay
being introduced?
thanks,
s.
On Wed, Aug 13, 2008 at 9:20 AM, Hideki Kato [EMAIL
Quoting Hideki Kato [EMAIL PROTECTED]:
Yes, UCT does. From my recent experiments with a delay
line (a fixed size FIFO queue) between a UCTsearcher and an MC
simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single
thread):
delay #po winsgames winning rateELO 1
steve uurtamo: [EMAIL PROTECTED]:
this is interesting!
perhaps i misunderstand the setup of the experiment -- what
is the unit of measure for the delay, or how is delay being
implemented?
the FIFO queue is doing what, and where is the delay
being introduced?
The UCT searcher pushes a position
Magnus Persson: [EMAIL PROTECTED]:
Quoting Hideki Kato [EMAIL PROTECTED]:
Yes, UCT does. From my recent experiments with a delay
line (a fixed size FIFO queue) between a UCTsearcher and an MC
simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single
thread):
delay#po
Mark Boon wrote:
Not an expert on AB-search or UCT search but there's a subtle
difference I think. In AB search, if some processors have been
searching in a branch that is subsequently cut off, the work is 100%
wasted. In UCT there's no such black-and-white cutting. If you do
sampling in what
On Wed, Aug 13, 2008 at 5:00 PM, Gian-Carlo Pascutto [EMAIL PROTECTED] wrote:
The problem is that the optimal settings for UCT appear to be much stronger
on the exploitation side than on the exploration side, making it much more
likely that such work is really wasted.
I'm not sure it's that
On Thu, Aug 14, 2008 at 12:00 AM, Gian-Carlo Pascutto [EMAIL PROTECTED] wrote:
Mark Boon wrote:
Not an expert on AB-search or UCT search but there's a subtle
difference I think. In AB search, if some processors have been
searching in a branch that is subsequently cut off, the work is 100%
Uct also has the advantage that it is much easier to use with multiple
CPUs. I know parallel alpha-beta exists, but my evaluation function is
not designed to be thread safe. If I put a big lock around it, there will
be almost no SMP scaling, since almost all the time is in the evaluation,
On Mon, 2008-08-11 at 20:39 -0700, David Fotland wrote:
Uct also has the advantage that it is much easier to use with multiple
CPUs. I know parallel alpha-beta exists, but my evaluation function is
not designed to be thread safe. If I put a big lock around it, there
will be almost no SMP
On Tue, 2008-08-12 at 09:15 +0200, Gian-Carlo Pascutto wrote:
On Mon, 2008-08-11 at 20:39 -0700, David Fotland wrote:
Uct also has the advantage that it is much easier to use with multiple
CPUs. I know parallel alpha-beta exists, but my evaluation function is
not designed to be thread
On Tue, 2008-08-12 at 09:15 +0200, Gian-Carlo Pascutto wrote:
Aside from that, it's not theorethically necessary for alpha-beta to do
wasted work (although it will in practise), and more CPUs can make the
program worse on any practical architecture (mostly due to locking and
memory
On 12-aug-08, at 10:40, Gian-Carlo Pascutto wrote:
On Tue, 2008-08-12 at 09:15 +0200, Gian-Carlo Pascutto wrote:
Aside from that, it's not theorethically necessary for alpha-beta
to do
wasted work (although it will in practise), and more CPUs can
make the
program worse on any practical
On 12-aug-08, at 10:40, Gian-Carlo Pascutto wrote:
Well... no. Because if you have a perfectly ordered tree, in theory,
you don't need to search at all.
You need to search it to *prove* that it's perfectly ordered :-)
--
GCP
___
computer-go
On Tue, 2008-08-12 at 15:40 +0200, Gian-Carlo Pascutto wrote:
On Tue, 2008-08-12 at 09:15 +0200, Gian-Carlo Pascutto wrote:
Aside from that, it's not theorethically necessary for alpha-beta to do
wasted work (although it will in practise), and more CPUs can make the
program worse on any
On Tue, 2008-08-12 at 15:40 +0200, Gian-Carlo Pascutto wrote:
Even in the theorethical case of a perfectly ordered game tree?
I'll have to check my facts, but I remember seeing actual numbers on
this. It has something to do with the minimial tree and it was a proof
think that alpha-beta
On Tue, 2008-08-12 at 15:40 +0200, Gian-Carlo Pascutto wrote:
On Tue, 2008-08-12 at 09:15 +0200, Gian-Carlo Pascutto wrote:
Aside from that, it's not theorethically necessary for alpha-beta to do
wasted work (although it will in practise), and more CPUs can make the
program worse on any
We need to define terms so we don't end up arguing about something we
probably agree on.
Here is my assertion (which I admit needs to be checked):
Given perfect move ordering, but not a-priori knowledge of this, a
parallel program will search more nodes on average than a serial
program. And
I wrote the evaluation in the early 1980s. Multicore and threads was far
from a consideration. The big issue was how to fit all the core data in 400
KB and make it fast enough to run well on an x286 processor at about 20 MHz.
:(
I wrote the playout code in April.
David
This doesn't really
On Aug 12, 2008, at 10:44 AM, Don Dailey [EMAIL PROTECTED] wrote:
We need to define terms so we don't end up arguing about something we
probably agree on.
Here is my assertion (which I admit needs to be checked):
Given perfect move ordering, but not a-priori knowledge of this, a
parallel
]; computer-go
computer-go@computer-go.org
Sent: Tuesday, August 12, 2008 8:17:35 AM
Subject: Re: [computer-go] Re: mogo beats pro!
On Aug 12, 2008, at 10:44 AM, Don Dailey [EMAIL PROTECTED] wrote:
We need to define terms so we don't end up arguing about something we
probably agree on.
Here
Don Dailey wrote:
We need to define terms so we don't end up arguing about something we
probably agree on.
Here is my assertion (which I admit needs to be checked):
Given perfect move ordering, but not a-priori knowledge of this, a
parallel program will search more nodes on average than a
Disraeli, Speech in the House of Commons [June 15, 1874]
- Original Message
From: Jason House [EMAIL PROTECTED]
To: [EMAIL PROTECTED] [EMAIL PROTECTED]; computer-go computer-go@computer-go.org
Sent: Tuesday, August 12, 2008 8:17:35 AM
Subject: Re: [computer-go] Re: mogo beats pro
Jason House wrote:
Maybe the best method is to mix the top down
style of MTD(f) to drive localized alpha beta searches.
MTD(f) *is* a sequence of alpha-beta searches.
I definitely don't have all the answers.
MTD(f) doesn't parallelize any better than normal alpha-beta. The only
] [EMAIL PROTECTED]; computer-go
computer-go@computer-go.org
Sent: Tuesday, August 12, 2008 8:17:35 AM
Subject: Re: [computer-go] Re: mogo beats pro!
On Aug 12, 2008, at 10:44 AM, Don Dailey [EMAIL PROTECTED] wrote:
We need to define terms so we don't end up arguing about something we
On Tue, 2008-08-12 at 18:18 +0200, Gian-Carlo Pascutto wrote:
Don Dailey wrote:
We need to define terms so we don't end up arguing about something we
probably agree on.
Here is my assertion (which I admit needs to be checked):
Given perfect move ordering, but not a-priori
Don Dailey wrote:
Here is an important snippet, but proofs follow in the paper:
The critical path length C is the time it would take for the program
to run on an infinite-processor machine with no scheduling overheads.
Note that it doesn't mention anything about useful WORK, because this is
On 10-aug-08, at 17:24, Don Dailey wrote:
Of course there is also the possibility of some exciting new hardware
breakthrough around the corner that doesn't just extend Moore's
law, but
blows it out of the water.
Of course there's that possibility. But I'm actually wondering if we
On Mon, 2008-08-11 at 10:19 -0300, Mark Boon wrote:
On 10-aug-08, at 17:24, Don Dailey wrote:
Of course there is also the possibility of some exciting new
hardware
breakthrough around the corner that doesn't just extend Moore's law,
but
blows it out of the water.
Of
On 10-aug-08, at 17:24, Don Dailey wrote:
Of course there is also the possibility of some exciting new hardware
breakthrough around the corner that doesn't just extend Moore's law, but
blows it out of the water. From: Mark Boon [EMAIL PROTECTED]
Of course there's that possibility. But I'm
On Mon, 2008-08-11 at 12:23 -0400, Robert Waite wrote:
Yes, but exhausitve search does not improve your player by 63% (eg.)
for a doubling in CPU time.
This part was done in an empirical scalability study. Please check the
archives of the list.
In the (inifinite) limit
On Mon, 2008-08-11 at 15:21 -0400, Robert Waite wrote:
You don't need to know the whole tree, you only need to know some of the
tree and it's a very small fraction of the whole. That's what
alpha/beta pruning is all about.
Certainly we are seeing gains by looking at smaller portions
On Mon, 2008-08-11 at 17:29 -0400, Robert Waite wrote:
Okay... congratulations... you are right... if you are able to
generate a completely pruned tree using alpha/beta pruning... you
don't have to generate the whole game tree. But exactly how are you
going to do this? In chess... you can look
We are in agreement on the general nature of things, but seeing it in
person was just so amazing. I did see comments about the quality of
the pro, but it may have been in the game chat rather than here. I
slept very little over the 10 days in Portland, so things are all
mixed up in my
It is of no consequence what words WE use to describe this. Journalists
will ALWAYS print it that way. If you use too many big words or ideas
that are accurate but convoluted, you will either not get the publicity
or the journalist will make up something even more absurd.
Sorry if I am a bit
I have a question. Why do you all call the game as human vs.
computer? It's obviously a match between Kim 8p and MoGo, a program
developped by MoGo team, running on a supercomputer.
Quick answer: it is the established term. (human-machine is perhaps
even more common?)
Longer answer: Mogo
Hi Darren,
Darren Cook: [EMAIL PROTECTED]:
I have a question. Why do you all call the game as human vs.
computer? It's obviously a match between Kim 8p and MoGo, a program
developped by MoGo team, running on a supercomputer.
Quick answer: it is the established term. (human-machine is
David,
I didn't intend to offend any person in this list, sorry for short
of my words. I'm just trying to prevent people misunderstand the
truth.
Hideki
David Doshay: [EMAIL PROTECTED]:
It is of no consequence what words WE use to describe this. Journalists
will ALWAYS print it that way. If
No offense at all taken by your words. I only meant to say that I
have had personal experience with how reporters and journalists
turn what they hear into what they write. It is my opinion that
we could try very hard to fix our words and they will either
change them back or make up something even
It does not change the fact MoGo was developped by the programmers.
And the fact the programmers spent many resources, like the people
fighting at Beijing right now, to develop MoGo.
And Kim was developed by his parents, his go teachers, go books, and
each opponent he has played against and
Sorry, but I can't let this statement go past. The go programs in the 90s
did local search, but not much global search. For example Many Faces did a
one ply global search, with a variable depth quiescence search. I added an
alpha-beta search to Many Faces last year, and it made a huge
On Mon, 2008-08-11 at 20:10 -0700, David Fotland wrote:
Sorry, but I can’t let this statement go past. The go programs in the
90s did local search, but not much global search. For example Many
Faces did a one ply global search, with a variable depth quiescence
search. I added an alpha-beta
.
David
-Original Message-
From: [EMAIL PROTECTED] [mailto:computer-go-
[EMAIL PROTECTED] On Behalf Of Don Dailey
Sent: Monday, August 11, 2008 8:31 PM
To: computer-go
Subject: RE: [computer-go] Re: mogo beats pro!
On Mon, 2008-08-11 at 20:10 -0700, David Fotland wrote:
Sorry
-Original Message-
From: [EMAIL PROTECTED] [mailto:computer-go-
[EMAIL PROTECTED] On Behalf Of Don Dailey
Sent: Monday, August 11, 2008 8:31 PM
To: computer-go
Subject: RE: [computer-go] Re: mogo beats pro!
On Mon, 2008-08-11 at 20:10 -0700, David Fotland wrote:
Sorry, but I can�t
Darren Cook: [EMAIL PROTECTED]:
It does not change the fact MoGo was developped by the programmers.
And the fact the programmers spent many resources, like the people
fighting at Beijing right now, to develop MoGo.
And Kim was developed by his parents, his go teachers, go books, and
each
Yeah, I am really on a roll ... first I am misquoted as saying it is
going to be all over for humans in go very soon, and then they say
I wrote GNU Go.
Sigh ...
I guess that now I need to expect requests for the next release of GNU
Go source, or Windows versions, or whatever.
Cheers,
At 01:50 AM 8/10/2008, you wrote:
Yeah, I am really on a roll ... ...
On 9, Aug 2008, at 9:34 PM, terry mcintyre wrote:
I was present; David Doshay said that in ten years, it would be
reasonable to expect computers to play even games with pros.
david d, do you *really* think that they will
Yes, for the first time I do think that on the 10 year time scale
computers will play against pros on an even basis. I am not
ready to predict that they will routinely beat the best of the
pros.
They play (or rather it played) at amateur 1-dan now ... that is
what just happened.
Cheers,
David
I'm sure you can find quotes from 'experts' claiming really wild
things on just about any subject.
I think generally that reaching 1-dan in computer-Go was thought to be
attainable with today's hardware but that it would still take
considerable work. I don't think MoGo's recent success suddenly
again, not true.
there are an infinite number of complexity classes beyond
P that do not require infinite space or infinite time.
exptime would just take exponential time instead of polynomial
time, and pspace would just be able to reuse its available
polynomial space (and thus use at worst
How do you know what [complexity] class go belongs in?
Hi Robert,
If these topics interest you, you probably want to start by reading the
papers [1] about the complexity of go. Then if you still disagree take
up a specific point with the paper authors.
Both minimax and UCT solve go simply
obedience is to commence tyranny in the nursery.”
Benjamin Disraeli, Speech in the House of Commons [June 15, 1874]
- Original Message
From: Don Dailey [EMAIL PROTECTED]
To: computer-go computer-go@computer-go.org
Sent: Friday, August 8, 2008 10:16:35 AM
Subject: Re: [computer-go] Re
From: David Doshay [EMAIL PROTECTED]
One point not discussed much in this thread is the consistency issue.
I think that if Kim were able to play a dozen games against mogo with
this same handicap he would win the last 6 ... people manage to adapt
and the computers do not.
But that much
, 1874]
- Original Message
From: Peter Drake [EMAIL PROTECTED]
To: computer-go computer-go@computer-go.org
Sent: Friday, August 8, 2008 1:48:23 AM
Subject: Re: [computer-go] Re: mogo beats pro!
Yes, MoGo gained much more from the longer time setting than Mr. Kim did. Note
that Mr. Kim
Don Dailey wrote:
Much the same as in GO, where 10 -15 years ago the idea of Dan level
play was so far off it was considered completely unattainable by
pessimists, and even optimists viewed it as a century away.
Where did you get that impression?
I've recently spent some time reading the
Don,
Regarding usage of time and computers and blitz games: human players in blitz
games tend to pick opening plays with good chances of success very rapidly from
their repertoire. Mogo seems to recreate opening theory from scratch for every
game; this makes it harder to win blitz games
Message
From: Don Dailey [EMAIL PROTECTED]
To: steve uurtamo [EMAIL PROTECTED]
Cc: computer-go computer-go@computer-go.org
Sent: Friday, August 8, 2008 11:38:57 AM
Subject: Re: [computer-go] Re: mogo beats pro!
It could probably be arranged using a modern quad processor or perhaps
an 8 processor
On Sat, 2008-08-09 at 03:49 -0700, terry mcintyre wrote:
From: David Doshay [EMAIL PROTECTED]
One point not discussed much in this thread is the consistency issue.
I think that if Kim were able to play a dozen games against mogo with
this same handicap he would win the last 6 ... people
On Sat, 2008-08-09 at 12:21 +0100, Matthew Woodcraft wrote:
Don Dailey wrote:
Much the same as in GO, where 10 -15 years ago the idea of Dan level
play was so far off it was considered completely unattainable by
pessimists, and even optimists viewed it as a century away.
Where did you
]
- Original Message
From: Don Dailey [EMAIL PROTECTED]
To: steve uurtamo [EMAIL PROTECTED]
Cc: computer-go computer-go@computer-go.org
Sent: Friday, August 8, 2008 11:38:57 AM
Subject: Re: [computer-go] Re: mogo beats pro!
It could probably be arranged using a modern quad
On Aug 9, 2008, at 8:30 AM, David Fotland wrote:
Unfortunately the Cotsen conflicts with the Taizhou tournament this
year.
David
Could you share some more details about this tournament?
Ian
___
computer-go mailing list
-
From: [EMAIL PROTECTED] [mailto:computer-go-
[EMAIL PROTECTED] On Behalf Of Ian Osgood
Sent: Saturday, August 09, 2008 8:50 AM
To: computer-go
Subject: Re: [computer-go] Re: mogo beats pro!
On Aug 9, 2008, at 8:30 AM, David Fotland wrote:
Unfortunately the Cotsen conflicts
Don Dailey wrote:
Matthew Woodcraft wrote:
Don Dailey wrote:
Much the same as in GO, where 10 -15 years ago the idea of Dan level
play was so far off it was considered completely unattainable by
pessimists, and even optimists viewed it as a century away.
Where did you get that impression?
-go] Re: mogo beats pro!
I tried to explain this to Chris Garlock about his misquote of what I
said, but he kind of shrugged it of in the name of getting the article
out on deadline. The mini-interview with me that he mentions in his
article was what happened when he asked me to proofread
Yes, MoGo gained much more from the longer time setting than Mr. Kim
did. Note that Mr. Kim used very little of his time in the one-hour
game. He said after the match that using more time would not have
helped him.
This is an interesting property of Monte Carlo Go. At the risk of
Yes, MoGo gained much more from the longer time setting than Mr. Kim
did. Note that Mr. Kim used very little of his time in the one-hour
game. He said after the match that using more time would not have helped
him.
I imagine that is typical as white in a handicap game; you play solid,
good
on this
supercomputer.
David
-Original Message-
From: [EMAIL PROTECTED] [mailto:computer-go-
[EMAIL PROTECTED] On Behalf Of steve uurtamo
Sent: Friday, August 08, 2008 2:45 AM
To: computer-go
Subject: Re: [computer-go] Re: mogo beats pro!
hm. this makes me think back to something.
did
not something he would necessarily do in a professional tournament.
perhaps true. money is a great motivating force, even small amounts
of money (as don has pointed out in the past).
s.
On Fri, Aug 8, 2008 at 7:57 AM, Robert Waite [EMAIL PROTECTED] wrote:
Yeah.. the misclick question is
To: computer-go
Subject: Re: [computer-go] Re: mogo beats pro!
hm. this makes me think back to something.
did this supercomputer have all of its ram shared
by all processors? or could it be emulated by
a large enough number of machines given individual
jobs, given that combining the results of those
Fantastic, as a long time list lurker I shall delurk for a minute to add my
congratulations to the Mogo team.
Ashley Rolleston.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
On Aug 8, 2008, at 7:13 AM, Robert Waite wrote:
I was in the KGS room for a couple of hours before the match and a
couple after. I was very surprised by the result as many were.
There still is a lack of clear information about the event. For
example, when Kim said that the computer plays
On Aug 8, 2008, at 7:57 AM, Robert Waite wrote:
Yeah.. the misclick question is another fuzzy point. There was a lot
of debate in the actual game about what was happening... but there
is the difficulty of having weak players and strong players
commenting. The only person who really knew
Kim applauded once when Mogo made a good move in a blitz game.
I believe that the comment about not using more time, which was in
response to my question, applied only to high handicap games.
Cheers,
David
On 8, Aug 2008, at 9:15 AM, Peter Drake wrote:
One person who seemed to be in
I think events like this are great. They generate interest and
excitement and are great fun.
But they have very little scientific value. They are wide open for
speculation, non-objective analysis, etc. Often strong players fail to
take matches like this seriously because they are
On Fri, 2008-08-08 at 09:44 -0700, David Doshay wrote:
One point not discussed much in this thread is the consistency issue.
I think that if Kim were able to play a dozen games against mogo with
this same handicap he would win the last 6 ... people manage to adapt
and the computers do
On 8-aug-08, at 14:16, Don Dailey wrote:
Also, it seems silly to me to find super strong players only to
heavily
handicap them. What's with that?
Actually, that's not so silly. I think a case can be made that super
strong players tend to have a more consistent level than weaker
On Fri, 2008-08-08 at 14:35 -0300, Mark Boon wrote:
On 8-aug-08, at 14:16, Don Dailey wrote:
Also, it seems silly to me to find super strong players only to
heavily
handicap them. What's with that?
Actually, that's not so silly. I think a case can be made that super
strong
don,
thanks for your thoughtful comments.
9 handicap is still a real game, in the sense that
the handicapping isn't arbitrary -- it definitely
measures some skill difference. i think that even
a match of 3 games would give quite a bit more
information, although i thought that Mr. Kim had
said
well, in opposition to the p neq np problem, this is a fixed
boardsize. it's an engineering, optimization, and special-purpose
algorithm issue at this point. no need for any solution to work
for all boardsizes in some measurable, scalable way.
s.
On 8/8/08, Robert Waite [EMAIL PROTECTED]
go is worse than np-complete, it's pspace-complete.
s.
On 8/8/08, Robert Waite [EMAIL PROTECTED] wrote:
well, in opposition to the p neq np problem, this is a fixed
boardsize. it's an engineering, optimization, and special-purpose
algorithm issue at this point. no need for any solution to
go is worse than np-complete, it's pspace-complete.
s.
I thought it was even worse than that ;)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
On Fri, Aug 8, 2008 at 11:07 PM, steve uurtamo [EMAIL PROTECTED] wrote:
i don't think that it's known to be exptime-complete.
http://www.ics.uci.edu/~eppstein/cgt/hard.html
E.
___
computer-go mailing list
computer-go@computer-go.org
On Fri, 2008-08-08 at 17:19 -0400, Robert Waite wrote:
If you mean that beating all human opponents would be solving go...
then I think it is certain that we will.
I would think the distance between perfect play and top human play is
quite far off.Beating the best human players is a good
2008/8/9 Don Dailey [EMAIL PROTECTED]:
This HAS (or is) happening in checkers. The best programs have only
tiny room for improvement. Play 100 games to get a score of 2 wins, 1
loss 97 draws (or something like that.) A major improvement is being
able to win 1 more game in 100. It's so
Yes, I know about Chinook and Jonathan Schaeffer is a friend of mine.
The PC programs also come with endgame databases, I think 6 piece is
real common and you can get up to 8 piece databases for your PC or
perhaps even more.
There is still a little life left in the top PC programs. Once in a
Besides... solving a
pspace-complete problem would require infinite memory... isn't that correct?
nope.
s.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
* Besides... solving a
** pspace-complete problem would require infinite memory... isn't
that correct?
*
nope.
I flipped memory and time there. If pspace-complete is not in p, then it
will be a big problem trying to solve it without infinite time. That doesn't
seem like an ideal
I flipped memory and time there. If pspace-complete is not in p, then it
will be a big problem trying to solve it without infinite time. That doesn't
seem like an ideal situation for solving it.
You only need an infinite amount of time for undecidable problems.
np-complete, pspace, exptime,
93 matches
Mail list logo
