In message <[EMAIL PROTECTED]>, Ian Phillipps writes:
: On Thu, 25 Oct 2001 at 12:56:21 +0100, Robin Houston wrote: : : > I suspect that I have a strange idea of Fun (perhaps I should start a : > list called "Fun with formal languages, complexity theory and : > non-standard logic", where I'll presumably be the only subscriber). : : Oh, I don't know :-) Me neither. :-) : > That's what PSPACE-complete means. If a problem is PSPACE-complete, : > that's a formal way of saying there's a snowflake's chance in hell : > that anyone will ever find a general algorithm to solve it quickly. : : Is it related to NP-complete? Yes, except it deals with space complexity rather than time complexity. NP-complete problems are the subset of NP to which all problems in NP are polynomial-time reducible (i.e., there exists a polynomial-time transformation that can convert an instance of some problem in NP to a problem in NP-compelte). That means that a fast solution to any problem in NP-complete would yield a fast solution for all problems in NP. (Note also that many encryption algorithms are trivially solved in nondeterministic polynomial time. Proving that P = NP would destroy current protections offered by cryptography.) PSPACE problems can be computed in a polynomial (in the size of the input) amount of space, but the time is unbounded. PSPACE-complete problems are the subset of PSPACE to which all problems in PSPACE are polynomial-time reducible. A fast solution to a problem in this class would be a miracle. : > PS. There's a CSG for generating prime numbers (including a delightful : > obfuscated C program) at http://members.fortunecity.com/brank/tor/primes/ : : .... but you can do that sort of thing with Perl's 'R'E, too: : grep {('x'x$_)!~/^(..+)\1+$/} 1..1000 : : or was that your point? The thread has passed me by :-) Perl's regular expressions are very powerful and much more powerful than what theoretical computer scientists mean by "regular expressions" (which can only recognize regular languages). For example, /^([ab]+)\1$/ accepts a particular CSL whose grammar would be a bitch to write. (You could use the pumping lemma for CFLs to prove that that aforementioned language isn't context-free.) Greg, having fun
