Hi I am new in this forum and I don't have any background in logic and computability. I had a question " How do you prove from the definition of logical ...
Hi, There are a couple books you might want to try. By now, a classic text is: Computational Complexity, by Christos Papadimitriou A more text-book like, but...
... a ... a ... language. ... [some lines of the original post is removed here.] ... to ... 1* ... we ... is ... decidable ... other ... Hello everyone, after...
If EQREX = {<R,S> : R and S are equivalent regular expressions}, how do I prove that EQREX is in PSPACE? I thought about converting R and S into NFAs, and then...
(sorry if this is a double post) if EQREX={<R,S> : R and S are equivalent regular expressions}, how do I show that EQREX is in pspace? I thought about...
(sorry if this is a double post) if EQREX={<R,S> : R and S are equivalent regular expressions}, how do I show that EQREX is in pspace? I thought about...
... do I show that EQREX is ... pumping lemma, but I ... strings iff R and S are ... Hello, Here is a possible solution. Convert R and S into nondeterministic ...
... some ... is ... decidable ... all ... is ... want ... not ... 4.12, ... (G)) ... ``tree ... where ... all ... k. ... by ... repeated ... Now ... test ... ...
Hello, I have a question about decidability. First, consider the following: * The language of all "empty" Context-Free languages is decidable; that is, the...
A friend asked me this question, and I wasn't sure how to go about it. Any help would be appreciated!: Prove that there is a language in P that is not...
... connection. ... The number of configurations of a 2DFA seems to be about the square of its input length. Therefore the time hierarchy theorem helps. ... ...
~~ ~~~ all my relations, the following two emails -- on the Lissajous Sinewave Functions which describe the helicoidal topology of creation -- were posted by...
Respected All, I have problem to solve this problem... Let L be the language of even strings. The twist of this language TWIST (L) is formed by exchanging...
Does the word even string mean "even-length string"? If so, then according to your definition of TWIST, the TWIST of an even string is just another even...
Dear all: I have a (historical) question about reduction and coNP. I know the defference between Karp's and Cook's reduction is the different results for the...
Well, by using a Turing reduction (Cook) instead of a many-one reduction (Karp), we haven't really learned anything more about the differences between P and NP...
~~ ~~~ ditto Doppel! truly, we know of no searcher before, to uncover and publish for all to see ... the simple details of the CREATION of matter!! the ancient...
Hi all. I've taken a pretty long hiatus from the group, but I hope to be back on a semi-regular basis again as I'll be heading back to school again in...
Hi Mike, Glad to see you back! In the text below: ... do you mean something along the following lines: You have a function convert that given integers n and b...
Hi, I would like to understand why is the recognition problem for chordal graphs in co-SL (complement of symmetric logspace). In [1] , the author argues that...
Hi Piotr! For your example, I'd have to say no--it is not representative of what I was poorly explaining. ... One place I used this technique was in a class...
Hi Nimish. I realize you wrote this way back in July. But while I'm reading up on the subject a bit, I was wondering (if you still watch this group), what the...
... chordal ... chordal ... ST ... of ... vertices s ... reduction. ... (2) ... Hello, hope the following helps. Consider the given characterization of chordal...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
