The most interesting open problem in computational complexity theory is the P vs. NP problem. Roughly, this problem is to determine whether a given problem can be solved as easily as it can be shown that a solution exists to the given problem. In his seminal work ValiantL. G. Valiant. Completeness classes in algebra. In Proc. of 11th ACM STOC, pp. 249–261, 1979. suggested an algebraic analog of this problem, the VP vs. VNP problem.
