Brian Jacobs

  • User since
  • Last active
  • Posted 5 times

About me

CMU ECE '16. Hobbyist interest in PL.

Recent activity

Posted in Who's Around?

Hi, all. I'm a hardware engineer working in high-speed ethernet. I took a lambda calculus course in college (with the wonderful Professor Statman of CMU) and have been a hobbyist fan of programming language design ever since. I have very little other background in PL, other than that I sometimes write parsers during my day job.

Posted in P = NP consequences

It's okay. I've certainly had worse mishaps with automated emails. :-)

I believe that I see an issue:

Let ff be a function which is computable in superpolynomial time, but verifiable in polynomial time. We define the inverse of this function, f1f^{-1} to be the function such that f1(y)={xf(x)=y}f^{-1}(y) = \{x \vert f(x) = y\}. Verification that f1=Xf^{-1} = X, for some set XX, involves computing f(x)f(x) for each xXx \in X. Computing each f(x)f(x) takes polynomial time, and the process of verification is linear in the number of elements in XX, and so verification for f1f^{-1} is computable in polynomial time.

But we need verification for f1f^{-1} to happen in superpolynomial time, otherwise f1f^{-1} cannot be outside of NPNP by definition. If f1f^{-1} is in NPNP, then our claim that f1Pf^{-1} \in P but f1NPf^{-1} \notin NP does not hold. This would mean that we do not have evidence of a function that is in NPNP but not in PP, which is central to the claim that PNPP \nsubseteq NP.

Posted in P = NP consequences

As a proof, let's take a general example of function AA that finds a solution in exponential and verifies a result in polynomial time. Now let's introduce its inverted function BB, and we have a general case in which solving and verifying swapped the calculating algorithms.

I'm not convinced that such functions necessarily have to exist. Take, for example, the graph isomorphism problem, which is classically understood to be in NPNP. To use the structure of this discussion, we'd say that we have a function ff which has a domain of the set of pairs of graphs, and codomain True, False. You can go from a pair of graphs to a boolean value uniquely, but cannot invert this function, since for both True and False there are multiple corresponding graph pairs.

Obviously, that there exists a single problem for which you cannot construct an inverse for the function doesn't imply that no function is reversible, but I'm having a hard time coming up with any function that has a domain and range of different size and is also reversible. Perhaps you could propose one, or at least a (possibly informal, possibly nonconstructive) proof that such functions should exist?

Posted in P = NP consequences

Firstly: I am definitely interested in your PP vs NPNP expository PDF.

The definition which I use, at least informally, is that a problem is in PP if there exists an algorithm which solves that problem in a number of steps which is related to the "size" of the problem instance by a polynomial function. A problem is in NPNP if there exists an algorithm which takes a solution to that problem and either verifies or disproves the correctness of that solution in polynomial time. (Where by polynomial time I mean the same as above.)

By this definition, the function of printing character bitmaps is in PP by building a lookup table from input character to output bitmap. Running through this lookup table to find the appropriate bitmap to return takes at most on the order of nn steps, where nn is the number of characters in the lookup table. If the number of characters is fixed at the definition of the function, then the runtime of this algorithm is at most on the order of O(n)O(n). Since nn is a polynomial, the problem is in PP.

The function of converting a bitmap back into a character is similar, albeit with a larger lookup table. The runtimes of these functions will therefore be fairly different; I would use the character \rightarrow bitmap function without reservation, but would probably try to find a more efficient implementation of the bitmap \rightarrow character one. Despite their differences in runtime, however, they have the same asymptotic complexity, and both reside in the complexity class PP.

Perhaps you could elaborate on how you are defining PP and NPNP?

Posted in Assumption: unbounded compute nodes?

I believe that what you are describing is the difference in algorithms analysis between work and span [0]. In brief, work is a measure of the total number of operations performed during a computation, while span is the length of the longest dependency chain between operations. I last talked about this as a freshman in a freshman algorithms class, so I can't point you to any literature (at least, not quickly), but you might be able to find references to those names.

The corollary about PP vs. NPNP doesn't seem very interesting to me, since all it claims is that the amount of time to solve certain problems grows slowly (or not at all) when you scale your computational resources to match the size of the problem. Perhaps I'm missing something of significance?

[0] See, for example, the definitions given in the overview section of