Talk:Computational complexity theory: Difference between revisions

Revision as of 17:10, 24 November 2009

Revision as of 18:50, 24 November 2009

Line 33:

{{FAOL|German|de:Komplexitätstheorie|small=yes}}

{{WP1.0|v0.7=pass|class=B|category=Mathematics|small=yes}}

==source==: ArXiv

http://arxiv.org/PS_cache/arxiv/pdf/0911/0911.4673v1.pdf

First, interesting algorithms:

F (string input) // F is a restricted type X program, for Q’ (f) is supposed to run in time P (n)

{

concurrent_ifs // only one of the returns can close the concurrent instructions block below, where

the two ifs run concurrently

{

{If (Simulated_by_Q [input]) return (0) ;}

{If (Q’ (f) = “Yes”) return (0); else return (1) ;}

}

}

Poly_Function (string input)

{

Into me, counter: = 0, n: = length (input);

For I: = 1 to n^10 {counter: = counter + 1 ;} // poly (n) bounded running time

If (counter > 100) return (1); else return (0);

}

(String input)

{

into I, counter := 0, n := length(input); for I := 1 to 2^n { counter := counter + 1; } // exp(n)

bounded running time if (counter > 100) return(1); else return(0);

}

S (string input)

{Remainder: = mod (integer (input), 2); // remainder on division of input (converted into integer)

by 2 if (remainder = 0) return (Fun2 (input)); // returns the value returned by Fun2 and halts if

(remainder = 1) return (Fun1 (input)); // never halts

}

Fun1 (string input)

{

Do {input: = “1” ;} while (1 = 1); // infinite loop

Return (1);

}

Fun2 (string input)

{

into I, counter := 0, n := length(input); for I := 1 to n^10 { counter := counter + 1; } // poly(n)

bounded running time if (counter > 0) return(1); else return(0);

}

excerpt:

The paper demonstrates three new revolutionary ideas in the foundations of Computational

Complexity Theory, against the established theory in the area:

1. Language Incompleteness: there are computational decision problems that are not languages

(may not be modeled as string acceptance testing to languages);

2. NP-Completeness Incompleteness: the Cook-Levin Theorem cannot in general be applied on an

instance of the XG+SAT to reduce it to an instance of the SAT, for a restricted type X program does

not necessarily halt for all inputs; and

3. SAT's weakness: the complexity class of the SAT maybe does not decide P versus

NP question <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/71.130.241.52|71.130.241.52]] ([[User talk:71.130.241.52|talk]]) 17:08, 24 November 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

==older entries==