On Wed, Oct 24, 2001 at 01:05:38PM -0500, Greg Bacon wrote:
> but my recollection is that determining whether a string is in a CSL
> is a problem in PSPACE (and maybe PSPACE-complete).
Yes, recognising CSLs is PSPACE-complete in general.
(CSGs are ridiculously powerful, *MUCH* more than Perl regular
expressions.)
> Can Perl regular expressions recognize all CSLs, though?
No, nor even all context-free languages. How about (a^n)(b^n)
(which is context free)? They slice across the Chomsky hierarchy
rather than slotting neatly into it.
> If for each k we had a specialized k-clique finder that runs in time
> polynomial in the size of the graph to be checked
We do. Here it is:
Successively generate the size k sets of nodes
(there are O(n^k) of them)
For each one, check whether it's complete
(can certainly be done in time O(k^2), which is constant as far
as we're concerned)
> then we'd have CLIQUE licked
Well then, licked it is! ;-)
> (and every other problem in NP-complete along with it).
It depends on the details of the particular reduction.
.robin.
--
Satan, oscillate my metallic sonatas!
