| [ QuizWit ] in KIDS 글 쓴 이(By): kimsr (Pabochet) 날 짜 (Date): 2000년 10월 30일 월요일 오후 05시 03분 54초 제 목(Title): Re: PSPACE-complete? Sorry I can't write in Korean right now. PSPACE-Complete means the hardest problems in the class PSPACE (obvious?). PSPACE is the class of problems that can be solved using polynomial space, that is, the problems can be solved using a memory of size polynomial of the input size. Some of the famous classes include P (polynomial time), NP (nondeterministic polynomial time), EXP (exponential time). It can be easily shown that EXP contains PSPACE. So far, we know that EXP contains PSPACE, PSPACE contains NP, and NP contains P. Someone proved that EXP properly contains P. Further, most all theory guys firmly believe that all three containments are proper. But so far we know only that at least one of the containments are proper. Interesting problem to think about, but don't expect you will find the answer. :) This is one advice everyone coming into this field receives. :) :) :( |