0
$\begingroup$

Let's define a "hand-incalculable problem" as a mathematical problem that can not be solved by available human calculation power (using only writing materials and utensils) at a specific date and geography, during lifetime of the person who posed the problem.

Given a specific date and problem can we strictly label the problem as "hand-incalculable"?

Edit:

We assume that algorithm to verify the solution is known.

Edit:

I am looking for a general classification similar to P/NP/NP-Complete which is used in computation theory. I wonder if we could define such classes for mathematical problems as HC(hand-calculable)/HI(hand-incalculable)/HI-Complete at any specific date. Even an absolute classification based on available human FLOPS and not related to a specific date, would be nice.

Edit:

  • HC: Hand-calculable at a specific date.
  • HI: Hand-Incalculable at a specific date.
  • HI-Complete: Hand-incalculable no matter how far mathematics will advance in future; consider a dynamic programming problem that needs millions of FLOPS of calculation power to be solved in reasonable time (during lifetime of the person who posed the problem).
$\endgroup$
2
+100
$\begingroup$

If you can determine big O for the problem and estimate calculations per hour for a person then you should be able to roughly determine your class.

This can, at most, be done for problems for which have algorithms to some them.

Also, since we can essentially be considered Turing machines, HI complete includes NC complete.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.