Re: michelson morley experiment questions
- From: Musatov <marty.musatov@xxxxxxxxx>
- Date: Tue, 30 Jun 2009 16:05:32 -0700 (PDT)
Martin Musatov wrote:
On Jun 30, 2:00 pm, cwldoc <cwl...@xxxxxxx> wrote:
On Jun 29, 3:37 pm, NoEinstein
<noeinst...@xxxxxxxxxxxxx> wrote:
[...]
What's more likely/ Five generations of physicists
missing something
basic, or a retired architect being wrong about
something he doesn't
understand?
What is the likelihood of an obscure clerk in a patent office coming up with revolutionary therories about the universe?
Thank God I am who I am.
If it is known that if any NP-complete language is sparse (contains no
more than a polynomial number of strings of length n), then P = NP.
[BH08] improved this result, showing that if any language in NP has an
NP-hard set of subexponential density, then coNP is contained in NP/
poly and thus, by [Yap82], PH collapses to the third level.
Conceptually, a decision problem is a problem that takes as input some
string, and outputs "yes" or "no". If there is an algorithm (say a
Turing machine, or a computer program with unbounded memory) which is
able to produce the correct answer for any input string of length
Failed to parse (<math_output_error>): n
in at most c \cdot n^k steps, where k and Failed to parse
(<math_output_error>): c are constants independent of the input
string, then we say that the problem can be solved in polynomial time
and we place it in the class P. Formally, P is defined as the set of
all languages which can be decided by a deterministic polynomial-time
Turing machine. That is,
P = {L:L = L(M) for some deterministic polynomial-time Turing machine
M}
where L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}
and a deterministic polynomial-time Turing machine is a deterministic
Turing machine M which satisfies the following two conditions:
1. M halts on all input w; and
2. there exists k \in N such that T_{M}(n)\in\; O(nk),
where T_{M}(n) = \max\{ t_{M}(w) : w\in\Sigma^{*}, \left|w
\right| = n \}
and tM(w) = number of steps M takes to halt on input w.
NP can be defined similarly using nondeterministic Turing machines
(the traditional way). However, a modern approach to define NP is to
use the concept of certificate and verifier. Formally, NP is defined
as the set of languages over a finite alphabet that have a verifier
that runs in polynomial time, where the notion of "verifier" is
defined as follows.
Let Failed to parse (<math_output_error>): L
be a language over a finite alphabet, Σ.
L\in\mathbf{NP} if, and only if, there exists a binary relation R
\subset\Sigma^{*}\times\Sigma^{*} and a positive integer k such that
the following two conditions are satisfied:
1. For all x\in\Sigma^{*}, x\in L \Leftrightarrow\exists y\in\Sigma^
{*} such that (x,y)\in R\; and \left|y\right|\in\;O(\left|x\right|^
{k}); and
2. the language L_{R} = \{ x\# y:(x,y)\in R\} over \Sigma\cup\{\#\}
is decidable by a Turing machine in polynomial time.
A Turing machine that decides LR is called a verifier for L and a y
such that (x,y)\in R is called a certificate of membership of x in L.
In general, a verifier does not have to be polynomial-time. However,
for L to be in NP, there must be a verifier that runs in polynomial
time. --MartinMichaelMusatov 07:18, 24 February 2009 (UTC)
NPC: NP-Complete
The class of decision problems such that (1) they're in NP and (2)
every problem in NP is reducible to them (under some notion of
reduction). In other words, the hardest problems in NP.
Two notions of reduction from problem A to problem B are usually
considered:
1. Karp or many-one reductions. Here a polynomial-time algorithm is
given as input an instance of problem A, and must produce as output an
instance of problem B.
2. Turing reductions, in this context also called Cook reductions.
Here the algorithm for problem B can make arbitrarily many calls to an
oracle for problem A.
Some examples of NP-complete problems are discussed under the entry
for NP.
The classic reference on NPC is [GJ79].
Unless P = NP, NPC does not contain any sparse problems: that is,
problems such that the number of 'yes' instances of size n is upper-
bounded by a polynomial in n [Mah82].
A famous conjecture [BH77] asserts that all NP-complete problems are
polynomial-time isomorphic -- i.e. between any two problems, there is
a one-to-one and onto Karp reduction. If that's true, the NP-complete
problems could be interpreted as mere "relabelings" of one another.
NP-complete problems are p-superterse unless P = NP [BKS95]. This
means that, given k Boolean formulas F1,...,Fk, if you can rule out
even one of the 2k possibilities in polynomial time (e.g., "if
F1,...,Fk-1 are all unsatisfiable then Fk is satisfiable"), then P =
NP.
--
Martin Musatov
.
- Prev by Date: - - Integrating factors and non-exact differential equations
- Next by Date: Re: Integral (Analysis qualifying exam problem)
- Previous by thread: - - Integrating factors and non-exact differential equations
- Next by thread: Re: michelson morley experiment questions
- Index(es):
Relevant Pages
|
