Theory
in [Programming]
|
C++ libraries pertaining to SAT Does anyone know if there are any C++ libraries available that deal with problems such as the boolean satisfiability problem? I'm looking for a library that would allow a programmer to test algorithms for solving 3SAT, SAT, and TAUTOLOGY. The more general and comprehensive the library, the better. I did a quic... 13 Jul 2008 17:10
NP vs co-NP Hello, why is it true that NP = co-NP if there is an NP-complete language L whose complement is in NP, too? My textbook argues as follows (cL denotes the complement of L): Because every NP language S is polynomial-time reducible to L, i.e. S<L if follows that cS is polynomial-time reducible to cL, i.e. cS<cL.... 13 Jul 2008 11:00
Context free languages Hallo, is there a simple argument to show that the word problem for context- free languages is in P? I can argue that the word problem of context sensitive ones is in NSPACE but I have no idea what to do with the context-free ones. Thanks, S. ... 13 Jul 2008 09:59
Turing computable function Hello, please let me state the core of my problem "Definition in computation theory" in a better way again. Is a partial function X - - f - -> Y Turing computable iff its graph, i.e. the set L_f={(x,y)|y=f(x)} is recursively enumerable? I think this is the case. What do you think? I would be very glad if ... 12 Jul 2008 12:33
Example for a non-rec.enum. language whose complement isn't rec.enum., too. Hello, I am searching for an example of a non-recursively enumerable language whose complement isn't rekursive enumerable, too. An example for a non-recursively enumerable language whose complement - is<- recursively enumerable should be the diagonal language, right? Thanks, S. ... 11 Jul 2008 16:07
Recursive set Hello, is it true that the set of ever-halting Turing machines (sometimes called 'algorithms') with alphabet {0,1} is not recursive but recursive enumerable? I think this is the case...but the truth don't care about what I am thinking :-). Thanks, S. ... 13 Jul 2008 02:51
Rice's theorem Hello, according to wikipedia, Rice's theorem says particulary "...this means that there is no machine that can always correctly decide whether the language of a given Turing machine has a particular nontrivial property." If I do understand the theorem correctly this is not true, I think. The theorem of Rice ... 14 Jul 2008 02:23
Symposium "Image Processing and Data Visualization" within the SEECCM 2009, Greece - Announce & Call for Papers (Our apologies for cross-posting. We appreciate if you kindly distribute this information by your co- workers and colleagues.) *************************************************************************** Symposium “Image Processing and Data Visualization” 2nd South-East European Conference on Computational Mech... 10 Jul 2008 09:16
BDD-package CUDD Hallo, can somebody help me? I want to call the function CountMinterm(...) of the BDD-package CUDD in my C++ code. I wrote DdNode * n = manager->ReadVars(0); double satc = manager->CountMinterm(n, varAnz); cout << "Es koennen " << satc << " viele Fahrzeuge gebaut werden." << endl; But I receive the erro... 10 Jul 2008 06:12
GI and CoNp Hi, reading in this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9811 on page 48 proposition 3.31 is written that GI (graph isomorphism) reduces to FI (formula isomorphism) but FI is coNp-Hard, so why this relationship is not enough to proof that GI is in CoNp? thanks a lot Regards FC ... 10 Jul 2008 06:12 |