if this is true, np!=p
 

(L(MN) in 2^n=>M in 2^n and n in 2^n) or (L(MN) in 2^n => M in 2^n and N in NP) I can prove this is false.

does that imply n,m are both in np? assume np=p and 2^n is the compliment np. if these are both in np, then L(MN) in np, but also 2^n. which mean 2^n and np overlap. np!=p.

it's a small statement but huge. I'm probably wrong, just wanted another's opinion.

Tom

L(M) Definition
 

L(M)="on input w nd select x in M such that |x|=|w|

for example, this L(M) would tell you what lengths of strings are accepted by M.

If n,m in NP then L(MN) in np

oops for L(M)... run x on M.

(L(MN) in np=>M in np and n in np) or (L(MN) in np => M in 2^n and N in NP). this statement is equivalent to the one I first stated. this statement is false.

Take M in 2^n. union it with sigma* of a one character abc. call this M*. M* is still in 2^n. But L(M*) is in P. L(M*) accepts every length because of the addition of sigma*.

Take L(M*N*) in P in NP. then the first statement in this block is false. because M* and N* are both in 2^n. but L(M*N*) in NP.

so with that statement false... the first statement in the first box is false. did I reach the right conclusion?

(L(MN) in np=>M in np and n in np) or (L(MN) in np => M in 2^n and N in NP).

should be (L(MN) in np=>M in np or n in np) or (L(MN) in np => M in 2^n or N in NP). it is equivalent to (L(MN) in 2^n=>M in 2^n and n in 2^n) or (L(MN) in 2^n => M in 2^n and N in NP).

the earlier example of L(M*N*) makes both statements false because in the first one here m and n can both be in 2^n.

a little help for those who might know theory of computation.

M a machine that takes in input w. that's all you need to know about machines for this proof.

boolean logic
a or b is only false if a and b are both false
a and b is only true if a and b are true
a implies b. if a is false then no matter what the statement is true. if a is true then the statement is false if b is false

compliments
the compliment of a and b is a compliment or b compliment
the compliment of a or b is a compliment and b compliment

P is polynomial time
NP is non deterministic polynomial time
2^n is exponential time

a good example of a np machine is L(M). say M runs in polynomial time. it has to pick an x that it thinks m will accept.. in real time this is exponential. that guessing can be said to be non deterministic and then the machine runs in polynomial time. so you put the non deterministic and polynomial time to get NP

I hope that helps for those of you not familiar with np?p

Tom

(L(MN) in np=>M in np and n in np) or (L(MN) in np => M in 2^n and N in NP).

ok, M* as described above, and take another, N*. Both 2^n machines. concatenate them and then take L(M*N*). L(M*)L(N*)=L(M*N*). both of those are in P. concatenate two thing in P, it's in NP. thus the first clause is false. M* and N* were both in 2^n. the second clause says that one is in NP. The fact that you can take L(M*N*) in NP means that there is at least one example where M is in 2^n and N is in 2^n.

the other statement is equivalent to this statement via contrapositives. if you would like me to explain that just yell, hey tom.

(L(MN) in np=>M in np and n in np) or (L(MN) in np => M in 2^n and N in NP).

This is false as seen previously. the contrapositive of a statement p => q is not q => not p. this might be wrong. here. because I forgot to switch p and q around, anyone see a fix?

(L(MN) in 2^n=>M in 2^n and n in 2^n) or (L(MN) in 2^n => M in 2^n and N in NP)

an equivalent statement is:
(M in np or N in NP => L(MN) in np) or (M in NP or N in 2^n=> L(MN) in NP)
counter example to prove this statement is false:
Take M in 2^n and concatenate with a machine that only accepts length 2 strings. N is in NP, M is in 2^n. so the left side is true, but L(MN) is in 2^n. this statement is false? so the equivalent statement is false. and the only way the equivalent statement is false is if M and N are in NP. thus L(MN) in NP. but L(MN) in 2^n.

Looks like you got a fairly nice conversation going on there, with your self. Frankly your theory scares me. At the rate we're going we'll see 8 long pages of computational theory, proving the non-existence of God and refuting that computers work in the first place.

it's two pages in word. and I found an error. it is new to computation theory that I know of. I've never seen L(M) in a book. just put it out there to see if any one agrees. I know it is a bit hard to digest. and it may be wrong.

THE PROOF?

L(M)="on input w nd select x in M such that |x|=|w|, run x on M.

(L(MN) in 2^n=>M in 2^n and n in 2^n) or (L(MN) in 2^n => M in 2^n and N in NP)
an equivalent statement is:
(M in np or N in NP => L(MN) in np) or (M in NP or N in 2^n=> L(MN) in NP)

counter example to prove this statement is false:
Take M in 2^n and concatenate with a machine that only accepts length 2 strings. N is in NP, M is in 2^n. so the left side is true, but L(MN) is in 2^n. this statement is false? so the equivalent statement is false. and the only way the equivalent statement is false is if M and N are in NP. thus L(MN) in NP. but L(MN) in 2^n.

Then (L(MN) in 2^n=>M in 2^n and n in 2^n) or (L(MN) in 2^n => M in 2^n and N in NP) is false. and the only way this is false is if M,N in NP then L(MN) in NP. but we started with L(MN) in 2^n.

sorry it took so long to get here. it's rather short.

Could you repeat the question please?--Maybe with just few less words....;)

Ma <y 3be m0r(e) words?

Unless someone was accidentally delivered a few truckloads of non-character symbols ... this might win the 'most incomprehensible thread' award.

Hands down...