I know that there are books written on this topic, so I'm probably full if sh-t. However, that dumb brain of mine felt like proving graphs to be isomorphic...
Sorry, guys! I found a significant flaw in my algorithm, and since Graph Isomorphism probably isn't in P, it's not likely I'll be able to fix it! Feel free...
I put in a couple more hours on it, and now the algorithm is giving correct results on the now many test-cases I've run. To get around the problem the...
Hi Bill, have you compared your algorithm with what is described in - http://scholar.google.com/ scholar?q=author:Hayes+intitle:%22On%20the%20Threshold%22 the...
... From: "Ashay Dharwadker" To: "Klaus D. Witzel" Subject: Four New Graph Algorithms Date: Tue, 26 Sep 2006 16:08:54 +0200 I have just updated my website with...
... From: "Ashay Dharwadker" To: "Klaus D. Witzel" Subject: Four New Graph Algorithms Date: Wed, 04 Oct 2006 11:26:11 +0200 ... graph in polynomial time... ......
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...
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.
