Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Computer scientists combine two 'beautiful' proof methods

quantamagazine.org

Post reply on HN
Print view View original

21–30 of 32 posts

Re: Computer scientists combine two 'beautiful' proof methods

#21

Post by ChadNauseam »

a1369209993 wrote: post #14
ChadNauseam wrote: post #12

Earlier quoted context omitted.

Wow, that is cool. I'm actually annoyed that vitalik didn't credit him in his article about them. I wonder how many people think that the v stands for vitalk

> vitalik didn't credit him in his article You mean this article? https://vitalik.eth.limo/general/2021/06/18/verkle.html > Verkle trees are still a new idea; they were first introduced by John Kuszmaul in this paper from 2018[link to [0]], 0: https://math.mit.edu/research/highschool/primes/materials/20...

Oh, I wonder if he edited it, I googled it to find what the GP was talking about and saw this which claimed he didn't: https://news.ycombinator.com/item?id=27557503

Re: Computer scientists combine two 'beautiful' proof methods

#22

Post by ChadNauseam »

ziofill wrote: post #17

A professor I know once gave me the most beautiful example of a zero knowledge proof: she said “Imagine I want to prove to you that I can count the leaves on a tree, but I don’t want to reveal how I do it. I start by telling you there are e.g. 756,912 of them. Then I close my eyes and I let you remove as many as you want. We can keep going until you are convinced, and you still won’t know how I did it.”

This is a nice example, but couldn't he add a constant to his count as long as he adds the same constant each time? Regardless, it's nice

Re: Computer scientists combine two 'beautiful' proof methods

#23

Post by ChadNauseam »

Zamiel_Snawley wrote: post #16
JohnKemeny wrote: post #9

Earlier quoted context omitted.

You have discovered that that problem indeed is not in NP, for the reason that it is not a decision problem. The decision problem is in NP, and there the problem is: given a graph and some value k, does there exist a TSP with cost at most k. You can see how that problem then becomes verifiable.

I think this is a great distinction that deserves elaboration for those less familiar with the topic. Can you explain a bit further?

A decision problem is a problem with a yes or no answer. An NP problem is one where a "yes" answer can be verified quickly if they also give you some proof or "witness" of it. If I say "is there a route that goes through all these cities that's less than 500 miles long", and you answer yes, you can prove that such a route exists by showing me one of these and I can simply check how long the route is. So the problem is in NP because a "yes" answer can be proven or checked quickly.

However, if you say "no, there is no such route", there's not obviously any way to quickly show that. Despite that, the problem is still in NP because to be in NP there only needs to be a quickly-checkable proof of a "yes" answer. If you want a quickly checkable proof of a "no" answer, you need a separate class of problem called co-np.

A problem can also be in np and co-np at the same time, if both "yes" answers and "no" answers can have a proof that can be checked quickly.

Re: Computer scientists combine two 'beautiful' proof methods

#24

Post by progval »

Zamiel_Snawley wrote: post #16
JohnKemeny wrote: post #9

Earlier quoted context omitted.

You have discovered that that problem indeed is not in NP, for the reason that it is not a decision problem. The decision problem is in NP, and there the problem is: given a graph and some value k, does there exist a TSP with cost at most k. You can see how that problem then becomes verifiable.

I think this is a great distinction that deserves elaboration for those less familiar with the topic. Can you explain a bit further?

In this context we can divide problems into two cases: optimization problems ("find a solution that satisfies P, in a way that has the highest score") and decision problems ("is there a solution that satisfies P, with score >= X" or "find a solution that satisfies P, with score >= X").

Complexity classes like NP are defined only for decision problems, not for optimization problems. NP can be defined either as

* the set of decision problems where, given a solution, you can check it in polynomial time with a deterministic Turing machine, or * the set of decision problems solvable in polynomial type by a non-determistic Turing machine

these two definitions being equivalent.

When someone mentions an optimization problem being in P, NP, or NP-hard, they actually mean the associated decision problem being in P/NP/NP-hard.

While technically incorrect, this is fine when working informally, because you can "translate" between the two in polynomial time.

If I give you an oracle (ie. a magic box) that solves an optimization problem (ie. gives you a solution to P with the highest score) immediately, you can trivially write a polynomial time algorithm that solves the decision problem: call the oracle, check the score of its answer, then compare that with the X value you were given. And vice versa: if I give you an oracle that solves a decision problem immediately (ie. given a value X, gives you a solution satisfying P with score >= X), you can write a polynomial time algorithm that uses the oracle a few times with the right values of X (exponential search then bisection), to find the solution with the highest score.

Re: Computer scientists combine two 'beautiful' proof methods

#25

Post by auggierose »

ziofill wrote: post #17

A professor I know once gave me the most beautiful example of a zero knowledge proof: she said “Imagine I want to prove to you that I can count the leaves on a tree, but I don’t want to reveal how I do it. I start by telling you there are e.g. 756,912 of them. Then I close my eyes and I let you remove as many as you want. We can keep going until you are convinced, and you still won’t know how I did it.”

Sorry, that doesn't make any sense.

Edit: From another comment, it starts do make sense. So you let them remove a number of leaves secretly, and then you tell them the new number again, and they can check if your answer makes sense because of the difference between the two numbers.

Re: Computer scientists combine two 'beautiful' proof methods

#26

Post by plank »

There seems to be a problem with the article: the example shown is with colouring the map. But showing two adjacent regions to have different colours proves nothing: they will always be different (if colouring is possible).

Perhaps if one shows two regions that do not share a border, and state that they are or are not the same colour...

Re: Computer scientists combine two 'beautiful' proof methods

#27

Post by akoboldfrying »

progval wrote: post #24
Zamiel_Snawley wrote: post #16

Earlier quoted context omitted.

I think this is a great distinction that deserves elaboration for those less familiar with the topic. Can you explain a bit further?

In this context we can divide problems into two cases: optimization problems ("find a solution that satisfies P, in a way that has the highest score") and decision problems ("is there a solution that satisfies P, with score >= X" or "find a solution that satisfies P, with score >= X"). Complexity classes like NP are defined only for decision problems, not for optimization problems. NP can be defined either as * the s…

Nitpick: Decision problems only have yes/no answers ("is there a solution that satisfies P, with score >= X"); problems that ask for actual solutions with a more complicated structure ("find a solution that satisfies P, with score >= X") are function problems, not decision problems.

Interestingly, even though the solution to a decision problem only gives you 1 bit of information, for all NP problems I'm aware of, solving a polynomial number of problem instances is still enough to recover a full solution. For example, suppose we're looking for a maximum clique in a graph. First, binary search as you describe to find the size of the maximum clique. Call that size X. Then to find an actual clique of size X, repeat the following for each vertex v in the graph, in any order:

1. Tentatively delete v and solve the problem "Is there now a clique of size >= X?".

2. If the answer is yes, delete v permanently: we can ignore it from this point on since there is some X-clique that avoids it, and we already know from our initial binary search that that clique is best-possible.

3. If the answer is no, v must belong to every X-clique in the graph. We can't do without it, so reinstate it in the graph.

Afterwards, exactly X vertices will remain -- the vertices of some maximum clique in the original graph.

Re: Computer scientists combine two 'beautiful' proof methods

#28

Post by ljlolel »

I once took a graduate level course at Princeton and the whole course for months was just spent understanding step by step the PCP proof. It was beautiful and subtle and had layers of complexity built on itself in layers. It was very hard —I can’t say I got it fully. (Arora himself taught it)

Zero knowledge proofs are way simpler to understand but also brilliant. I applaud Quanta's effort to try to explain both these concepts.

I love to learn the limits of our knowledge and what is provable and how to exploit that for fun and profit.

Re: Computer scientists combine two 'beautiful' proof methods

#29

Post by olddustytrail »

ChadNauseam wrote: post #21
a1369209993 wrote: post #14

Earlier quoted context omitted.

> vitalik didn't credit him in his article You mean this article? https://vitalik.eth.limo/general/2021/06/18/verkle.html > Verkle trees are still a new idea; they were first introduced by John Kuszmaul in this paper from 2018[link to [0]], 0: https://math.mit.edu/research/highschool/primes/materials/20...

Oh, I wonder if he edited it, I googled it to find what the GP was talking about and saw this which claimed he didn't: https://news.ycombinator.com/item?id=27557503

From your link:

vbuterin on June 19, 2021 | prev | next [–]

Thanks! I actually wasn't aware of the intellectual history. I added a link to your paper at the start of my post.

Re: Computer scientists combine two 'beautiful' proof methods

#30

Post by Ar-Curunir »

ChadNauseam wrote: post #2

I know cryptocurrencies have a lot of problems, but this is one place where it’s good they exist: they’ve funneled a ton of money into researching new cryptography. The article claims that this research was developed for StarkWare, which developed its own form of zero knowledge proofs they called Starks, developed a programming language in which cryptographic proofs can be generated showing that the output of the pro…

This research was not developed by Starkware. STARKs (and indeed many other SNARKs) use techniques like those in this work, but the authors are not related to Starkware in any way
Post reply on HN