| [ QuizWit ] in KIDS 글 쓴 이(By): kimsr (Pabochet) 날 짜 (Date): 2000년 11월 6일 월요일 오후 04시 33분 55초 제 목(Title): Re: 5x5 바둑 Maybe you were too steamed to see that I have answered the first time you asked. :) Yes I did, as plainly as possible. You just didn't see. Oh, and you need a reason for that. I'll give you some reasons, although you will eventually see that you can accept my statement without them, let alone the definition of PSPACE. Consider the sorting problem. Consult any algorithm text if you don't know what sorting is. (Don't ask me for definitions you can find in many many texts.) How many possible configurations the sorting problem has? Obviously, it is n!. (This is used in proof of a lower bound for sorting.) How hard is the sorting problem? It is very easy because it is solved in (n*log n) time. Now consider the knapsack problem. In knapsack problem, you are requested to find a subset from a set of n numbers that sums up to a given number S. How many configurations are there? Yes, there are only 2^n configurations. But, alas, this problem is NP-Complete, which consists of damn hard-to-solve problems. (But these are, or people believe they are, easier than Go.) Now I know what you will ask. Do I have a proof that knapsack is harder than sorting? No, I don't. But, there is some other problem that I do have a proof. This problem is called regular expression matching. Have you used a regular expression? In DOS or Windows, you sometimes use expression such as abc*.exe. This is an example of (a restricted) regular expression. I won't give you a definition of this particular problem because it is a bit too long to fit in the already too long document. You may just think of it as a problem consisting of a pattern (like abc*.exe) and a string in which you are requested to judge if the pattern matches the string. In the regular expression matching problem, the input consists of characters from a finite alphabet. So, the number of possible configurations are C^n for some constant C, larger than 2^n but still much less than n!. Let me introduce another jargon here. There is a class of problems called ELEMENTARY. This class consists of the problems that can be solved in time proportional to (or less than) any of 2^n, 2^(2^n), 2^(2^(2^n))),... . So, this class consists of many many problems way way harder than Go. There are many versions of the regular expression matching problem. One version allows for the NOT operator. I'll assume you know what that means. This version of regular expression matching problems is not in ELEMENTARY! And you wondered why vi (the UNIX editor) didn't have a NOT operator in its regular expressions... :) So, basically, regular expression matching is way harder than sorting, even though it has apparently much smaller possible configurations. Please, don't change your channel. I'm not finished. Real fun starts here. Things I have mentioned above are actually not needed here! What was that you wanted from me? You wanted some reasons for my statement! Let me repeat my statement here. "The number of possible configurations does not necessarily indicate the hardness of a problem." What am I saying here? In strict mathematical sense, I'm just stating a tautology. The above statement says something may or may not indicate some property. This statement is true whatever that something or some property may be! So you really don't need any reason to understand my statement. I wonder what kind of answers you can produce now you have some unneeded reasons for this tautology to hold. What you said is a lot different. You said one problem is not harder than another problem because the first has smaller possible configurations that the second. In other words, what you said is "The number of possible configurations indicates the hardness of a problem." This is obviously not a tautology and we do need a reason for this. Hence, it eventually turns out that you are the one who needs to provide some kind of reason to support your statement. :) Can you see why I didn't give you the definition of PSPACE? The last thing you need to understand that you are wrong is the definition of PSPACE. Do I need the definition in any part of this document????? :) |