Theory

NP with oracle machines
Hello, I have a question pertaining to the complexity class NP and oracle machines. Suppose you are dealing with the class NP relative to a particular oracle machine, say one for SAT or TQBF. If you wanted to actually physically compute membership to a language that belongs to this complexity class, what w... 7 Jul 2008 19:42

FCT 2009 conference known?
Hi all, Does anyone know where (and maybe when) the next FCT (International Symposium on Fundamentals of Computation Theory) will be held? The 2007 conference site does mention an 'invitation to FCT 2009' but the place is not mentioned. thanks, Johan ... 5 Jul 2008 09:27

How many edges are there in semi cubic digraph
How to understand follow digraph: " a simple strong connected digraphs with at most indegree 1 or 2 and outdegree 2 or 1 respectively" (let named it as semi cubic digraph) I think there are at most m=3n/2 edges existance in the semi cubic digraph with n vertecies But a reviewer think that a cycle digrap... 5 Jul 2008 23:44

Question on Sipser example proof
I'm a complete newbie to computation theory, so unfortunately my question(s) are likely to seem really naive. This has to do with an example from Sipser's Theory of computation, 2nd Edition, page 24 to 25. It's an inductive proof of loan calculation. He's proving this. P sub t = PM^t - Y(M^t -1/M -1) ... 5 Jul 2008 21:42

Word problems for grammars
Hello, i am sorry for asking another pack of questions but sadly I don't know what I should do otherwise to get answers to problems I am stuck on. 1. You can speak of problems (which are always word problems to me) in P and NP without giving any alphabet because it does not matter, i.e. if you formulate a prob... 4 Jul 2008 08:58

Complexity theory
Hello, I have a few questions on complexity theory which are perhaps easy to answer for an expert or perhaps at least for a beginner in the field. 1. Is the problem CLIQUE(n) that decides weather an input graph has got an n-clique or not in NP? I suppose it is, because I know that CLIQUE (that gives the maximal... 7 Jul 2008 13:31

Second CALL FOR PAPERS: WfPM'08, September 2008, Timisoara, ROMANIA
2nd CFP: Workshop on Workflow and Process Management (WfPM'08), September 2008, Timisoara, Romania EXTENDED DEADLINES ______________________________________________________________________________________________ WfPM'08 -- Workshop on Workflow and Process Management in conjunction with SYNASC-2008 10th Inte... 2 Jul 2008 16:01

Word problem for boolean expressions
On Jul 2, 9:11 am, sanchopanch...(a)web.de wrote: Hello, if you consider the alphabet S={\wedge,\vee.\not,(,),x,0,1} one can think of all boolean expressions B as a language over this alphabet. Is the problem of deciding weather a string s of S* is in B or not in P? My guess is that the easiest way to s... 2 Jul 2008 12:55

Diffused concern for too many papers on PvsNP
We know that there are hundreds of people around who think they have solved PvsNP. The history of math is full of similar situations: Open problems attract the attention of many. It seems that on this occasion, I mean PvsNP, there is enormous concern, especially in blogs, regarding the number of naive papers. ... 5 Jul 2008 14:33

VMCAI 2009: Call for Papers
=============================================================================== ------------------- CALL FOR PAPERS ------------------- VMCAI 2009 The Tenth International Conference on Verification, Model Checking, and Abstract Interpretation ... 29 Jun 2008 14:12