User talk:Jasper Deng/Archive 24

Archive 20

←

Archive 22

Archive 23

Archive 24

Archive 25

Archive 26

→

Archive 30

Balloon problem

While I seriously doubt we will ever come to any agreement about the problem statement, I have a gut feeling that your problem boils down to taking a set of numbers (I believe they will be integers) and seeing if you can sum them up to a specific value. As an example, if I have the integer A, B, and C and I want them to sum up to D, I am looking for xA+yB+zC=D. The issue is that there are two problems. One is "What are the values for x, y, and z?" The other is "Is there an x, y, and z that can solve the first problem?" The "is there a solution" version, which is what I believe you asked, is much easier. First, you can easily answer no if all of the values of A, B, and C are negative and D is positive. Similarly, if A, B, and C are all positive and D is negative, the answer is no. As long as at least one of A, B, or C is the same sign as D, there is *a* set of values x, y, and z that will solve the problem. But, that doesn't mean that there are integer values of x, y, and z that solve the problem. Further, it doesn't tell you what those values might be. Do you agree with this so far or am I still way off on your problem? 209.149.113.4 (talk) 12:11, 2 November 2016 (UTC)

@209.149.113.4: You have exactly described the NP-complete problem I reduced from - unbounded subset sum, which is a similar yes-or-no problem and is NP-complete. So short of proving P = NP you're never going to find a polynomial time algorithm that even answers "yes or no" correctly all the time, even without explicitly finding an answer. The same goes for other NP-complete problems like 3-SAT. In general, a decision problem is indeed usually a simple yes/no question. It's also false that you'll always be able to find an answer, even if one of A, B, and C have the same sign as D, because I have constrained x, y, and z to be integers. The problem instance with D = 7, A = -2, B = -4, C = 6 has no solution because no integer linear combination of even numbers will make an odd number. The restriction to integers is important - linear programs over Q are solvable in polynomial time (as alluded to by other commenters on that thread) while the decision version of integer linear programming is NP-complete. Note that rephrasing the unbounded subset problem to allow rational linear combinations makes it trivial: if A, B, C... are all zero, then there is no solution unless D = 0 as well, otherwise (without loss of generality) A is nonzero, then we can set x = D/A and y, z, ... = 0.

My original problem is at least as hard as this problem for it imposes further constraints; having an integer linear combination of wind vectors reaching your destination is necessary but insufficient for a solution to my problem.

Once again, you demonstrate that you need more experience with theoretical computer science. If you even bothered to read my reduction, you would have noticed that this doesn't matter.--Jasper Deng (talk) 15:26, 2 November 2016 (UTC)

The difference between the subset sum problem and your problem is that you have multiples of each integer. That is a huge difference. As you appear to have already noticed, getting a sum of zero when multiples are allowed for all integers is trivial. Your complication is that one of the integers is required and cannot have a multiple. That still deviates from the subset sum problem. Allowing for an infinite supply for all the other integers means that I only have to show what the minimum difference is in the set. In your example of {-2, -4, 6}, the minimum difference is 2. So, with that set, I can get any result of n*2. If n must be an integer, n*2 will never equal 7. If it was a problem where the answer was 'yes', I still wouldn't know what the answer might be. I would just know that the destination result is a multiple of the minimum difference and, therefore, there is an answer. I admit that I'm not taking into account the number of times you can go up/down in this part of the discussion. I'm merely trying to explain why I don't see how this reduces properly to the subset sum problem - which doesn't mean that I haven't read what you wrote. I merely disagree with what you wrote. I am happy to continue discussing this with you if you like. You are handling this discussion very well compared to the students (and often professors) that I normally talk to. In reality, this is the time of year that I am flooded with students who just realized that they don't know how to handle a two-dimensional array or somehow skipped every class that discussed how pipelining works. But, I fully understand if you do not want to discuss it. I will only respond if it appears that you want a response. 209.149.113.4 (talk) 17:31, 2 November 2016 (UTC)

@209.149.113.4: You again did not seem to read my reduction (and clearly you don't understand what a "reduction" is - I don't care about reducing it to the subset sum problem because like every problem in NP, this problem can be reduced to it - I'm interested in proving it's NP-complete, which requires a reduction from another NP-complete problem). The unbounded subset sum problem is also NP-complete. Want proof? It's in the paper I linked among others. The unbound subset sum problem still only allows you to have non-negative coefficients (and importantly, not all of which can be zero - this is a requirement of the original subset sum problem too), so it is not an arbitrary Z-linear-combination, so one cannot simply look at the ideal generated by the numbers in the set we have (as you propose): the example with A = 6, B = 3, C = 5, D = 4 has no solution either, even though 1 is the "minimal difference". In fact, I should even correct myself here: the instance where A = B = C = 0 actually has no solution because of the requirement for a nonempty solution multiset. Also, a problem in NP can be a simple yes/no question not requiring constructive proof of "yes". The only requirement is that if we have a certificate (i.e. "evidence" the answer is yes), we must have a polynomial time verification algorithm.

The unbounded subset sum problem, or the (equivalent) version of this problem where the target sum is not 0, but some other arbitrary number (the proof of this equivalence is left as an exercise for the reader), is shown to be NP-complete in Computers and Intractability. The other equivalent version can also be reduced to the balloon problem by setting point B to be equal to the desired sum.

I'm not claiming to be an expert in this field, but it's clear to me that you aren't reading what I'm writing/wrote. I'm not sure what you're wondering about, but if it is the NP-completeness of the unbounded subset sum problem, make sure you understand precisely what that problem means, and refer to various publications that accept it as NP-complete.

If you don't understand what I wrote, that's a different thing, and I thank you for asking! But if it's that you don't understand my reduction, then you need to ask and explicitly tell me that!--Jasper Deng (talk) 19:05, 2 November 2016 (UTC)

It appears that the gap between what you are writing and what I am reading is far to wide to cross, but I do admire your enthusiasm. I haven't been lucky to have many enthusiastic students or colleagues since I left California (I think proximity to Silicon Valley is strongly correlated to computer science enthusiasm ... not implying that you must be from California or that you are worse off if you aren't). To the problem: The minimum difference in {7, 3, 5} is 3 since there is no negative value to compare the positive values to. There is no n such that n3 = 4. So, I can easily say that there is no solution. In the example you previously had and replaced, the minimal difference for {-9, 3, 5} is 4. There is an n such that n4=4. So, there is a solution. You don't compare same signed numbers for difference, only opposite signed numbers. Then, you ignore multiples. This is based on a proof of the Chinese Remainder Theorem that I read decades ago. It is what immediately comes to mind when looking at this problem (just the "can I make a sum", not the entire "balloon" problem). In that proof, it was shown that the subset sum problem was not NP if multiples were allowed. I'm sorry that we are obviously miles apart in our understanding of looking at the same text. 209.149.113.4 (talk) 20:04, 2 November 2016 (UTC)

@209.149.113.4: I have since updated my problem. You may claim P = NP if you want, but in general your "minimal difference" method is doomed for failure. For example, it would incorrectly answer "no solution" for the instance A = -3, B = 5, C = 9, D = 27, because 27 is not even, even though there's the obvious solution x = y = 0, z = 3, and also the solution x = 6, y = 9, z = 0 or x = 6, y = 0, z = 5. A less trivial example with more than 3 elements in the set is the set {-1, 4, 8, 16} with target value 107. Again, the minimal difference is 3, and 107 is not divided by any of the numbers in question, but there is the obvious solution 1(-1) + 25(4) + 1(8) + 0(16) among many others. In fact, it would erroneously conclude that whenever the minimal difference is greater than one, and the target number is prime, larger than the minimal difference, and not one of the integers in the set, there is no solution - which is false in general. In particular, the Chinese remainder theorem does not apply here because the numbers are not coprime, and we have negative numbers in the mix as well. So the problem is not equivalent to "is my target number an integer multiple of the minimal difference". Have you read the text I linked for the proof of the NP-completeness? Another source is Knapsack Problems by Hans Kellerer, Ulrich Pferschy, David Pisinger (page 492).

It is also wrong that this problem is not in NP. A solution multiset is a certificate for any "yes" answer, and obviously all we need to do is add up all those elements to show the validity of the solution, a polynomial time operation. This is the definition of NP.--Jasper Deng (talk) 20:13, 2 November 2016 (UTC)

I'm sorry, but I still see this as being far too similar to asking if ax+by=c for some value of x, y, and c. You are allowing multiples of x and y, so you have the a and b to contend with. I've tried to nudge you back through time, hoping to eventually get to Diophantus. It is clear that you simply won't have it. Please continue to pursue this and you should eventually see that you can turn it into a linear Diophantine equation. You don't need to solve the equation to get a "yes" or "no" answer. However, solving those equations is very simple. Then, adding the part about going up and down is a twist that I don't feel will change the solution much. 209.149.113.4 (talk) 12:05, 3 November 2016 (UTC)

@209.149.113.4: 2-SAT can be solved in polynomial time while 3-SAT is NP-complete, even though both are so similar - so "similar" doesn't cut it. In particular, ax + by = c can be efficiently solved like you said, and in fact, introducing a 3rd variable can be most likely solved efficiently (based on what I've been reading on the coin problem), but not an arbitrary amount of variables, as in the general problem. You have offered no rigorous proof of any method, while I have cited multiple reputable texts that establish NP-completeness of unbounded subset sum. And in any case, given that you earlier did not understand what I meant by a "reduction", you appear to be unqualified to be talking about complexity theory - I've been replying primarily for your benefit, but I doubt you understand what I mean by "NP-complete", nor do you seem to be willing to look at the sources yourself. And in general, solving systems of linear Diophantine equations with the variables constrained to be nonnegative is also NP-complete via reduction from subset sum (the proof of this is left as an exercise); for a single Diophantine equation (again with variables constrained to be nonnegative - that is important!), the unbounded subset sum problem shows that it too is NP-complete in general. Your comment is very hand-wavy, whereas mine are rigorously grounded in complexity theory - you must have a rigorous understanding of the concepts here to be having a formal discussion about it. --Jasper Deng (talk) 14:38, 3 November 2016 (UTC)

Apparently, this still bugs you. I still disagree with the claim that this absolutely must be an NP-complete problem. I see that you have a set of variables (x, y, z...) and you want to come up with a set of constants (a, b, c...) such that ax+by+cz... = d. The constraint is that all values of all variables and constants must be integers. I believe that the entire argument centers on the fact that you do not see it as ax+by+cz... = d. They way I see it, it is a linear Diophantine equation (I know that it is also listed as a denumerant problem and as an unbounded knapsack problem). Therefore, all previous work with linear Diophantine equations apply. My point, from my very first statement, is that asking "is there a solution" is often easier than "what is the solution". Getting a solution for a linear Diophantine equation is a counting problem and known to be #P. Asking if a solution exists is a very different question. Papadimitriou, Faliszewski, and Hemaspaandra are, to my knowledge, still debating this (and I plan to discuss it with them at conference in July). They all agree that if all variables are positive, it is #P-complete to ask "is there a solution." What if some are negative? I posed that I could convert a linear Diophantine equation with negatives in one that only contains positives and therefore, it would be #P-complete. That was shot down quickly because I would be adding extra constraints on the constants. Until I see proof that it is NP (or more precisely, #P), I will continue to state that it is possible that the "is there a solution" question might not be NP. 209.149.113.4 (talk) 19:33, 14 November 2016 (UTC)

@209.149.113.4: I also saw that it's a linear Diophantine equation - with the variables constrained to be nonnegative, and I happen to have had the pleasure of learning from Papadimitriou himself on this subject. I already told you countless times to look at Knapsack Problems which proves that unbounded sum is NP-complete, by reduction from 0-1 subset sum. Linear Diophantine equations without the variables constrained to be nonnegative are easy, but that's a very important constraint.

And I'm not interested in Sharp-P as a complexity class, because my problem as formulated is a decision problem. General decision problems in NP are just as hard as problems that ask "constructively find me one solution".

If what you are asking for is a proof sketch, I can happily provide it at a later time (I am about to go off and do something else). But again, I doubt you'd understand. You did not even get the order of the reduction in question correct, and as before, "not NP" is clearly false - this problem most certainly is in NP.--Jasper Deng (talk) 19:44, 14 November 2016 (UTC)

You are correct that the Knapsack Problem is NP as an optimization problem. Asking "does a solution exist" is different. What if I can approximate a solution? It isn't optimal, but it is a solution? That is what I work with, approximate solutions to NP problems. Technically, they are called "fully polynomial time approximate solutions." The knapsack problem does have a FPTAS. The textbook I use for reference is "Approximate Solutions" by Vazirani. I admit that it is considered a "dirty" science. Who really wants an approximate solution? But, it answers the question "does it exist" and often there is a fully polynomial time approximation. That goes back to the only point I've intended to make: There *may* be a polynomial time answer to "does it exist" for your original problem. 209.149.113.4 (talk) 20:38, 14 November 2016 (UTC)

@209.149.113.4: Yes, it's possible that P=NP. That's not related to whether this problem is NP-complete though. --Jasper Deng (talk) 20:43, 14 November 2016 (UTC)

@209.149.113.4: By the way, my original gut feeling about my original problem was that it had to have an efficient solution. Results of NP-completeness can be surprising and I spent hours convincing myself my reduction was correct (see also my proof sketch below). And on the subject of approximation algorithms, first off, the concept is not a priori defined for decision problems, and second, the approximation algorithms we know can't be used to find an exact (i.e. always correct) solution to the decision problem. Otherwise we would not be asking if P = NP. --Jasper Deng (talk) 18:44, 17 November 2016 (UTC)

For interested readers, my original problem can also be easily proven to be NP-complete using reduction from ordinary (0-1) subset sum. Refer to the proof I supplied there (beginning with "In fact,"). We can enforce there being only one of each subset item by modifying the proof as follows: Change the dimension of the position vector space to |S| + 1; set A = 0 and B = (T, 1, 1, ..., 1) for the target value T. Recall that at odd-numbered heights 2l - 1 (where l ranges from 1 to |S|), I specified that v would be the lth set member. Now instead let v be (S_l, 0, ..., 1, 0, ..., 0) at odd-numbered heights 2l - 1, and (0, 0, ..., 1, 0, ..., 0) for even numbered heights 2l, where the 1 appears at the (l + 1)st component of v. Now using multiple instances of a member of the set causes the (l + 1)st component to be greater than 1 and thus missing the target, so any solution only will have at most one instance of every member of the set. K_up and K_down will need modification, too, but this is just a sketch.

I also spoke with Papadimitriou today and he affirms that the unbounded subset sum problem is indeed NP-complete.--Jasper Deng (talk) 08:18, 17 November 2016 (UTC)

LINK

Can you leave me a link to "Infobox Musical artist", because i cant find it, even after searching--Wyatt2049 (talk) 20:44, 17 November 2016 (UTC)

ArbCom Elections 2016: Voting now open!

Hello, Jasper Deng. Voting in the 2016 Arbitration Committee elections is open from Monday, 00:00, 21 November through Sunday, 23:59, 4 December to all unblocked users who have registered an account before Wednesday, 00:00, 28 October 2016 and have made at least 150 mainspace edits before Sunday, 00:00, 1 November 2016.

The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to impose binding solutions to disputes between editors, primarily for serious conduct disputes the community has been unable to resolve. This includes the authority to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail.

If you wish to participate in the 2016 election, please review the candidates' statements and submit your choices on the voting page. MediaWiki message delivery (talk) 22:08, 21 November 2016 (UTC)

2016 PTS

Hi Jasper, As per usual we are now over 200000b for the PTS article and as a result I am looking at all of the sections in order to try and clean them up. As a part of this earlier, I removed some information relating to Meranti's intensity in comparison to Winston and the list of most intense tropical cyclones which I felt was trivial, when your looking at telling the story of Meranti since there are 4 typhoons which make the list this year thus far. The other part is that the JTWC and their intensity estimates are unofficial and we have to remember that most of the world is based on 10-min winds. I also noticed that we are currently saying that Winston had the exact same 1-minute winds as Meranti. However, you reverted fairly as you felt that "Meranti was notable for its intensity estimates and this should be reflected here." As a result I think we need to work together to find a solution to both of our concerns.Jason Rees (talk) 20:37, 4 December 2016 (UTC)

@Jason Rees: Meranti had higher 1-minute winds than Winston and that is reflected in the article ("surpassing..."). Instead, it would be better to cut down on the excessive information on the storm's meteorological history (which belongs in the storm's own article). And I only recall three typhoons making the list (Nepartak, Meranti, Haima) this year (Chaba fell short at 905). The sub-900 pressure definitely merits mentioning that Meranti made the name.--Jasper Deng (talk) 20:47, 4 December 2016 (UTC)

Ok I misread both Chaba and Meranti's estimates and yeah i agree that the MH should be cut down to size while being cleaned up. I have made several seasons GA quality and would love to take a PTS there if we could all pull together on it. However, I still disagree that it should be mentioned that it made the list, especially when you consider that to the best of my knowledge the list isn't replicated anywhere else.Jason Rees (talk) 21:37, 4 December 2016 (UTC)

BBC 12-hour Editathon - large influx of new pages & drafts expected

AfC Reviewers are asked to be especially on the look out 08:00-20:00 UTC (that's local London time - check your USA and AUS times) on Thursday 8 December for new pages. The BBC together with Wikimedia UK is holding a large 12-hour editathon. Many new articles and drafts are expected. See BBC 100 Women 2016: How to join our edit-a-thon. Follow also on #100womenwiki, and please, don't bite the newbies :) (user:Kudpung for NPR. MediaWiki message delivery (talk) 00:02, 8 December 2016 (UTC)

Merry Christmas and happy holidays!

Hello Jasper Deng: Enjoy the holiday season and winter solstice if it's occurring in your area of the world, and thanks for your work to maintain, improve and expand Wikipedia. Cheers, Doug Weller talk 15:23, 25 December 2016 (UTC)

Spread the WikiLove; use {{subst:Season's Greetings}} to send this message

Nock-ten dissipation?

JMA still clearly states a TD (former Nock-ten) active as of 27/12 18Z. I'm sure we talked about this before and stated that if JMA doesn't show a TD or system (in its Weather maps) then it had already dissipated. Typhoon2013 (talk) 22:35, 27 December 2016 (UTC)

@Typhoon2013: Wikipedia talk:WikiProject Tropical cyclones#Using JMA weather maps to extend western Pacific storm tracks needs to stop.--Jasper Deng (talk) 22:36, 27 December 2016 (UTC)

I'll just leave a message in there starting now. Typhoon2013 (talk) 22:39, 27 December 2016 (UTC)

Happy New Year, Jasper Deng!

Happy New Year!

Jasper Deng,
Have a prosperous, productive and enjoyable New Year, and thanks for your contributions to Wikipedia.
Codename Lisa (talk) 07:18, 1 January 2017 (UTC)

   Send New Year cheer by adding {{subst:Happy New Year fireworks}} to user talk pages.

FYI: you cannot ping anon editors

Just in case you did not know, see Wikipedia:Notifications#Triggering_events. Tigraan^{Click here to contact me} 11:19, 11 January 2017 (UTC)

Template:Infobox hurricane current

I don't understand what your issue with the improvements that were made to this template are, but reverting all the changes just because some text is not bold is preposterous. If you would like text to be bold that is not currently bold, there is the sandbox. Or you can post on the talk page and request a change be made. --Zackmann08 (^{Talk to me}/_{What I been doing}) 05:20, 20 January 2017 (UTC)

@Zackmann08: It's not even just that. Cosmetically, I think your version is not as good as the previous (code-wise, yes it is good to re-use {{Infobox}}) in terms of spacing and text size. I'd highly suggest asking at WT:WPTC before making such a change to an important infobox - this is not a typical infobox either, as it is more intended as a status indicator (akin to the vandalism meter above on my talk page) than a usual infobox.--Jasper Deng (talk) 06:45, 20 January 2017 (UTC)

A consensus has LONG been reached to make all Infobox templates use {{Infobox}} and you are reverting a MASSIVE change because you "think it looks ugly that the text is not bold". That is absurd. --Zackmann08 (^{Talk to me}/_{What I been doing}) 06:54, 20 January 2017 (UTC)

@Zackmann08: And it is completely in line for me to revert a massive change when I don't agree with it - and cosmetic reasons are very valid reasons to revert. Per BRD, you should not be reinstating your change before you settle the dispute over it.

I would fix it myself, but I don't understand your code right now, and would rather have you fix it since you designed the change. --Jasper Deng (talk) 06:57, 20 January 2017 (UTC)

Iseult exists, Harriet never exists

Hi, after I looked to the 1970 South-West Indian Ocean best track from Tropical Tidbits, I saw that Iseult formed in there, I also looked that Harriet never formed in the Australian region, here: http://www.tropicaltidbits.com/data/TC/SI/tracks/1970.png So that means, there was no Harriet-Iseult, just Iseult, if that information is not true, please tell me. Abdullah Almarri - A.W.S.T. (talk) 07:42, 23 January 2017 (UTC)

(talk page stalker) @Abdullah Almarri - A.W.S.T.: Look at the map there very carefully - Do you see that Iseult supposedly formed right on the border of the Australian region which was 80E for a number of years before it was changed.Jason Rees (talk) 17:57, 7 February 2017 (UTC)