Content deleted Content added
→Table or list?: ok |
No edit summary |
||
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
==older entries==
| |||