Theory

Hamiltonian cycle problem in 2-connected bipartite cubic graph is Polynomial
Determining a Hamiltonian cycle in 2-connected bipartite cubic graph had been claimed as a NP-completed problem by Akiyama etc. Now we show that this problem is in polynomial, thus this is the second case for P =NP which checked not only by testing but also by pure mathematics (the detail will show latter). ... 25 Dec 2007 22:43

A New Reduction Rule for Exactly 1 in 3 SAT
I have improved the reduction rule to work with any variable, not just pure literals. I still assume no two clauses contain more than one variable in common. This is guaranteed with these three reduction rules: X() = X3SAT instance (a,b,c) = exclusive 3SAT clause (choose exactly one literal to be True) X... 6 Jan 2008 06:39

Please help (Multi-commodity)
Hello, I have posed a scheduling problem as a multi commodity flow problem and solved it . I need to prove that my problem is NP complete. I know that the multi-commodity problem is NP complete. How would i go about solving this ??? any tips ???? Your help is greatly appreciated. Thanks Arush ... 22 Dec 2007 15:54

MultiCommodity Flow
Hello, I have posed a scheduling problem as a multi commodity flow problem and solved it . I need to prove that my problem is NP complete. I know that the scheduling problem is NP complete. How would i go about solving this ??? any tips ???? Your help is greatly appreciated. Thanks Arush. ... 21 Dec 2007 17:52

AMAST 2008 - Call For Papers
[Apologies for multiple copies.] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % The 12th International Conference on % % Algebraic Methodology and Software Technology % % AMAST ... 21 Dec 2007 10:24

Minimalization operator on recursively enumerable predicate
Hi all, I've little trouble seeing why, for recursively enumerable predicate Q(x,y), the function defined as a(x) = ìy Q(x,y) (ie. minimalization operator for variable 'y' applied on Q(x,y)) is not partially recursive function. Could someone help me seeing this please? Thank you for every suggestion. ... 20 Dec 2007 04:40

Passing of Phyllis Winkler
I posted this over in the TeX news group and c.t. is the next group in my .newsrc: A small obit caught my eye which noted the passing of Phyllis Winkler. Phyllis died Dec. 7. But she was much more, she was an institution unto herself at the Stanford CS Dept. (which was at least mentioned in the obit). She will ... 18 Dec 2007 18:46

How does the inverse Ackerman function arise in complexity theory
Hi folks, I've seen some complexity bounds expressed in terms of the inverse Ackerman function. Can someone explain how such a function arises in the derivation of a complexity bound? In other words, does anyone have a reference for a derivation of a complexity bound that includes the Ackerman function? Tha... 18 Dec 2007 18:46

Call papers to AUTOMATA 2008
============================= FIRST ANNOUNCE: Apologies to multiple posting ============================= AUTOMATA 2008 Future of Cellular Automata Theory and Applications June 12-14 2008 Bristol, United Kingdom We are inviting you to participate in the international workshop on cellular automata. The un... 10 Dec 2007 00:50

Concerning the Labels of Edges in the State Diagram of a PDA
In Sipser's "Introduction to the Theory of Computation", he states: We write "a,b -> c" to signify that when the machine is reading an a from the input it may replace the symbol b on the top of the stack with a c. Any of a, b, and c may be epsilon. If a is epsilon, the machine may make this transition without rea... 10 Dec 2007 00:50