tag:blogger.com,1999:blog-3722233.post2261093677532727451..comments2024-08-06T20:16:40.851-05:00Comments on Computational Complexity: What is the complexity of these problems and metaproblems?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-16257191052063498952010-08-09T04:07:12.511-05:002010-08-09T04:07:12.511-05:00here is a proof of P=NP, give me some comment http...here is a proof of P=NP, give me some comment http://www.anhphamillusion.co.cc/website/pversusnp.htmlanh phamhttp://www.anhphamillusion.co.cc/website/pversusnp.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60860438147111611742010-08-01T01:29:41.322-05:002010-08-01T01:29:41.322-05:00The first problem you ask is equivalent to determi...The first problem you ask is equivalent to determining Schur numbers. The number s(t) is the minimum n such that any t-coloring of the positive integers up to n has a monochromatic solution to x+y=z. The problem you ask is essentially the inverse function of s(t). It is known that s(t) is at least exponential in t (the best known exponent follows from blowing up a small case), and at most a constant times t!. Closing the gap is a famous problem in Ramsey theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25907142580342767322010-07-31T20:52:23.907-05:002010-07-31T20:52:23.907-05:00The original problem has an easy upper bound of ce...The original problem has an easy upper bound of ceil(log_2(n)), just partitioning into groups 2^(k-1)...(2^k)-1, since each pair in the k-th box has a sum at least 2^k. Proving that this is optimal seems harder.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71789450019098075852010-07-31T14:03:50.644-05:002010-07-31T14:03:50.644-05:00Jason,
1) I have edited the post to
include a cla...Jason,<br /><br />1) I have edited the post to<br />include a clarification.<br /><br />2) Reading it your way, you show<br />that you can use just n/3 boxes.<br />Can you do even better than that?<br />I think you can- just put all of<br />the numbers in ONE box and always<br />assign x,y,z so that x+y\ne z.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74110233572604505062010-07-30T23:53:37.962-05:002010-07-30T23:53:37.962-05:00I don't have one right now, give me some more ...I don't have one right now, give me some more time to think about it. I wished you had included the statement, "x,y,z are ANY number in the box". Without the any, the solution is trivial. The ANY, implying all combinations of x y and z to the 3 numbers in the box, changes the problem from what you had originally stated. I was thinking of the problem as it was layed out.<br /><br /> If x, y, and z are in a box, then it cannot be that x + y == z. Nowhere in the original statement makes any claims about x,y,z taking all permutations of the numbers in the box and all of those permutations still have to hold to the x + y =/= z. This makes things tougher, but varies in important ways from the question you asked.<br /><br />If I go with my first reading of the problem, I can give you a solution that will tell you exactly how many boxes you will need. Since the original statement makes no claims to how x, y, and z get assigned, this leaves me to do the assigning. put the first 3 numbers in box 1, with the highest lowest number being tagged as z. Put the next 3 numbers into box 2, with the lowest number tagged as z. Repeat until you are out of numbers. In this scenario, from what I first read of the problem, you will need: [;\left \lceil \frac{n}{3} \right \rceil;]Jasonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61623991266857667682010-07-30T18:52:55.760-05:002010-07-30T18:52:55.760-05:00Last anon- you seem to be talking about
just one c...Last anon- you seem to be talking about<br />just one case of the problem.<br />Do you have a solution, trivial or not,<br />that will, given n, tell me the MIN number of boxes to place 1,...,n<br />such that if x,y,z are ANY numbers in a box then x+y NE z ?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41547908723061991272010-07-30T17:05:37.545-05:002010-07-30T17:05:37.545-05:00Maybe it's specified better in the original pr...Maybe it's specified better in the original problem, but there's nothing saying that z has to be the largest number in the box. If box 1 has the numbers 1, 2, and 3, set z == 1. 2 + 3 != 1. This trivializes the problem into ceil(n / 3) boxes. Arguing definitions and going against the spirit of the problem, but I see nothing dictating how the numbers are to be labeled, leaving the choice up to you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63745820773573621152010-07-30T09:31:10.120-05:002010-07-30T09:31:10.120-05:00It looks like the partition problem where
you want...It looks like the partition problem where<br />you want to split a set of numbers into<br />2 sets with equal sums.<br /><br />In PARTITION there are only 2 parts but the E depends on n.<br /><br />In my problem you have k parts but E has<br />only a fixed number of variables.<br /><br />The ability to let a_1,...,a_n be whatever you want makes me think that some<br />trick with coding things into bits might work.<br /><br />But I don't really know.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26350475707455008672010-07-30T07:20:24.376-05:002010-07-30T07:20:24.376-05:00{ (a1,...,an,k,E) : there exists a way to partitio...{ (a1,...,an,k,E) : there exists a way to partition {a1,...,an} into at most k boxes so that no box has x1,...,xm with E(x1,...,xm)=0 } I suspect this is NPC. <br /><br />why do you suspect this is NPC?<br /><br />I want to know more about thisAnh Phamhttps://www.blogger.com/profile/18346153321030289601noreply@blogger.com