Motivation: One thing I've wondered about is whether mathematical concepts and problems are what they are simply because of human choices and history, or whether there are certain concepts and problems that are intrinsically important. The problem stated below attempts to crystallize this by asking about circuits that can solve some range of problem instances of some NP problem, and whether they all focus on the same group of instances.

Math: Let $L$ be a fixed language, and $d$ some fixed integer, and let $L_d$ be the subset of $L$ consisting of words of length bounded by $d$. Fix $\epsilon,k$ and consider the set $C$ of circuits of at most $k$ gates which correctly classify at least $\epsilon T$ of all words of length $\leq d$ as in or out of $L_d$, where $T$ is the total number of all words of length $d$ in the alphabet of $L$. I am interested in questions like, for a given word $s$, what is the expected number of circuits in $C$ that correctly classify $s$? What about conditional on there being at least one such circuit? What is the variance? What is the dependence on the various parameters $L,d,k,\epsilon$?

I suspect this kind of question is difficult to answer, but are there any relevant heuristics or conjectures? Can anything be said conditional on standard assumptions?

Edit: The connection between the two parts is supposed to be the following: one of the things mathematicians try to do is create good algorithms for solving problems (I think a lot can be boiled down to this, ultimately), where "good" is some combination of effective and feasible. If all the good algorithms concentrate on the same collection of problem instances, then we might expect that any mathematicians (like the titular Martians) would wind up being able to solve the same kinds of problems. On the other hand, if the distribution is more even, it might just be a matter of taste which instances to focus on. I would also be interested in anyone who has a better idea of what formal problems could capture some of the question in the motivation.

  • 3
    $\begingroup$ The actual question is sensible, but I fail to see its connection to Martians and to human history. $\endgroup$ – Emil Jeřábek Aug 17 '16 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.