GeneralThis forum is for non-technical general discussion which can include both Linux and non-Linux topics. Have fun!
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
(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.
(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
(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.
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.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.