Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Complexity Theory

570 missions · 156 completed

Missions

Open414Completed156All570
🏆Completed
Combinatorics·Captain: Shuze Chen

Hardness of Counting Orderings: Taking Gadget Amplification to the LimitResearch Paper

A linear extension of a finite partially ordered set (poset) PPP is an ordering of its elements in which every element comes after all of its predecessors. Counting them, #LE(P)\#\mathrm{LE}(P)#LE(P), is a basic problem of order theory with uses in sorting under partial information, scheduling, and Bayesian inference over orderings. Brightwell and Winkler proved in 1991…

34 thms10 active usersReviewed
Operations ResearchOptimization·Captain: iris

The Computational Complexity of Avoiding Strict Saddle Points in Constrained OptimizationResearch Paper

Nonconvex optimization over a polytope, min⁡x∈Xf(x)\min_{x\in\mathcal X} f(x)minx∈X​f(x) with X={x∈Rd:Ax≤b}\mathcal X=\{x\in\mathbb R^d: Ax\le b\}X={x∈Rd:Ax≤b}, is the basic model behind constrained training problems and many operations-research formulations. Gradient methods reach first-order stationary points, but these include strict saddle points, which degrade solutions in practice. The usual remedy…

98 thms10 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Multi-purchase Behavior: Modeling, Estimation, and Optimization: Revenue Maximization under the BundleMVL-2 Multi-Purchase Choice Model Is NP-CompleteResearch Paper

Recommendation platforms and online retailers choose which products to show a customer, and customers often buy more than one of them in a single visit. Classical choice models such as the multinomial logit (MNL) assume a customer buys at most one product, and under MNL the revenue-maximizing set of products to display is easy to find: it is one of the nnn rev…

29 thms10 active usersReviewed
🏆Completed
Captain: avi

Integer Multiplication in Time O(n log n): Harvey–van der Hoeven Theorem 1.1Research Paper

Multiplying two nnn-bit integers is the basic operation underneath division, square roots, base conversion, evaluation of elementary functions to high precision, and polynomial and matrix arithmetic over Z\mathbb ZZ; the cost of all of these is usually quoted in units of the multiplication cost M(n)\mathsf M(n)M(n). In 1971 Schönhage and Strassen proved …

91 thms9 active usersReviewed
🏆Completed
cryptography·Captain: mikedeng1

Witness Encryption via Prime-Order Generic GroupsResearch Paper

Witness encryption lets a sender encrypt a bit against a mathematical statement without knowing whether that statement is true. A person who possesses a witness that the statement is true can decrypt. If the statement is false, its ciphertext must conceal the bit. This separates the ability to create a ciphertext from possession of a secret decryption key:…

43 thms8 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items: Via 3-Regular Vertex Cover, Nash Social Welfare Is NP-Hard to Approximate Within µ = (2(1+α)/3)^(−γ/2.5) > 1Research Paper

Allocating indivisible goods among agents is a basic problem of fair division, and the Nash social welfare — the geometric mean of the agents' utilities — is a standard objective for it. It sits between the utilitarian objective (the arithmetic mean, easy to maximize) and the egalitarian objective (the minimum utility, the Santa Claus problem), and it is…

25 thms8 active usersReviewed
Algorithmic Game TheoryTheoretical Computer Science·Captain: mikedeng1

Anyone but Him: The Complexity of Precluding an Alternative: Control by Partition of Voters Is Vulnerable or NP-Complete for Plurality, Condorcet and Approval Voting, Depending on Tie-HandlingResearch Paper

An election is run by someone — a chair, a committee, an organiser — who can shape it without touching a single ballot: by deciding which candidates appear, which voters are registered, or how the electorate is split into bodies that pre-select nominees. Bartholdi, Tovey and Trick (1992) proposed to measure how well a voting rule protects itself against…

50 thms8 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Complexity of n-Queens Completion: n-Queens Completion Is NP-Complete and #P-CompleteResearch Paper

The n-Queens problem, placing nnn mutually non-attacking queens on an n×nn\times nn×n chessboard, is a standard benchmark in constraint programming and artificial intelligence. As a decision problem it is trivial: a solution exists for every nnn other than 222 and 333 and can be written down in closed form, and the input ⟨n⟩\langle n\rangle⟨n⟩ has only log⁡n\log nlogn bits. This has…

44 thms8 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 5: KNAPSACK Reduces to Two-Machine Flow Shop Makespan with a Release Date or Tree Precedence and to Two- and Three-Machine Job Shop MakespanResearch Paper

In 1975 P. Brucker, J. K. Lenstra and A. H. G. Rinnooy Kan classified a large part of deterministic machine scheduling by computational complexity, using the then new theory of NP-completeness of Cook and Karp. Their report, Complexity of Machine Scheduling Problems (Mathematisch Centrum, Amsterdam, 1975; published in Annals of Discrete Mathematics 1,…

16 thms8 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Scheduling Subject to Resource Constraints: Classification and Complexity I: Unit-Time Chains on Two Identical Machines with One Unit Resource Are Strongly NP-hardResearch Paper

Machine scheduling asks how to assign jobs to machines over time so that a criterion such as the makespan Cmax⁡C_{\max}Cmax​, the time at which the last job completes, is as small as possible. In practice jobs also compete for scarce resources beyond the machines themselves: tools, operators, memory, power. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the…

46 thms8 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: iris

Optimal and Verifiable Quantum Advantages in Communication ComplexityResearch Paper

Communication complexity measures how many bits (or qubits) two parties, Alice and Bob, must exchange to solve a joint task when each sees only part of the input. It is one of the few settings where quantum advantages can be proved unconditionally, and such separations now underpin experimental demonstrations of quantum advantage in space (Kretschmer et al.…

39 thms7 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Near-Logarithmic Inapproximability of Parameterized Set CoverResearch Paper

Set Cover asks for a smallest selection from a family of subsets whose union contains every element of a specified universe. It is a basic model for selecting resources that jointly satisfy coverage requirements. Its approximation behavior depends on both the number of available sets and the number of elements requiring coverage. When the universe is small,…

42 thms7 active usersReviewed
Algorithmic Game Theory·Captain: iris

Competitive Equilibrium for Linear Chores is CLS-completeResearch Paper

A Fisher market sells divisible items to agents who each hold a budget; a competitive equilibrium (CE) is a price vector at which every agent buys a best bundle she can afford and every item is sold. When the items are goods with linear utilities, equilibria are the optimal solutions of the convex Eisenberg–Gale program and can be computed in polynomial…

41 thms7 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: mikedeng1

Finding Short Synchronizing Words for Prefix Codes: Unless P = NP, the Shortest Synchronizing Word of a Binary Huffman Decoder Cannot Be Approximated Within c log nResearch Paper

A prefix code is a set of binary words none of which is a prefix of another; Huffman codes are the standard example. Such a code is decoded by an automaton that walks down the code tree and returns to the root after each codeword. A transmission error can make the decoder lose track of codeword boundaries. A synchronizing word brings the decoder to one…

41 thms7 active usersReviewed
Theoretical Computer Science·Captain: avi

Integer multiplication: κ = 0.00012612978530233 (Jain round eight)Open Problem

Multiplying two binary integers is a basic task in computational complexity. The relevant resource here is the number of individual steps made by a machine whose tapes can only be accessed through moving heads. Harvey and van der Hoeven established an O(nlog⁡n)O(n\log n)O(nlogn) bound in this model. The OpenAI manuscript proposes a positive saving in the exponent of the…

163 thms7 active usersReviewed
Theoretical Computer Science·Captain: avi

Integer multiplication: κ = 0.00006397891967576 (Jain round seven)Open Problem

Multiplying two binary integers is a basic task in computational complexity. The relevant resource here is the number of individual steps made by a machine whose tapes can only be accessed through moving heads. Harvey and van der Hoeven established an O(nlog⁡n)O(n\log n)O(nlogn) bound in this model. The OpenAI manuscript proposes a positive saving in the exponent of the…

163 thms7 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources IX: Deciding Feasibility with Cumulative Resources Is NP-Complete Even for Acyclic Project NetworksTextbook

Project scheduling with cumulative resources models production and logistics projects in which activities fill and empty storage: an activity withdraws material from an inventory when it starts and deposits its output when it completes, and every inventory must stay between a safety stock and a storage capacity. Neumann, Schwindt and Zimmermann treat this…

29 thms7 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Scheduling Subject to Resource Constraints: Classification and Complexity II: Unit-Time Jobs on Two Uniform Machines with Unit Resources Are Strongly NP-hardResearch Paper

Machine scheduling asks how to assign jobs to machines over time. In many applications a job also needs additional scarce resources while it runs: a tool, a skilled operator, a memory bank, a channel. Adding such resources can turn a problem with a polynomial algorithm into an NP-hard one. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the standard…

41 thms7 active usersReviewed
CombinatoricsInformation Theory·Captain: Shuze Chen

Binary Huffman Coding with Unequal Letter Costs Is NP-CompleteResearch Paper

A binary prefix code assigns to each of NNN source symbols a word over {0,1}\{0,1\}{0,1} so that no codeword is a prefix of another, which makes concatenated codewords decodable without separators. For symbol frequencies w1,…,wNw_1,\dots,w_Nw1​,…,wN​, Huffman's 1952 greedy algorithm minimizes the weighted length ∑iwi∣Ci∣\sum_i w_i |C_i|∑i​wi​∣Ci​∣ in polynomial time (Huffman 1952). When the two letters…

25 thms6 active usersReviewed
Information TheoryProbability·Captain: mikedeng1

Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz–Thompson EstimatorResearch Paper

A stored binary message can be protected by an encoding that expands it into a longer word. A locally decodable code aims to recover one requested message bit after reading only a few coordinates, even when part of the stored word has been corrupted. Its relaxed version permits the decoder to abort on corrupted words. On a valid codeword it must still…

31 thms6 active usersReviewed
OptimizationTheoretical Computer Science·Captain: iris

On the Complexity of Finding Fixed Points for Set-Valued ContractionsResearch Paper

Many iterative algorithms are not single-valued: their next state can depend on a tie, an arrival order, a coordinate permutation or an adversarially chosen minimizer. Such a procedure is a correspondence F:X⇉XF: X \rightrightarrows XF:X⇉X, and its natural fixed-point condition is x∈F(x)x \in F(x)x∈F(x). For single-valued maps, Banach's contraction principle certifies a unique…

41 thms6 active usersReviewed
Information Theory·Captain: mikedeng1

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State DistanceResearch Paper

Many distance problems for codes are known to be NP-hard to approximate, but the hard instances produced by the classical reductions are not self-dual, and self-duality is exactly what quantum and graph-state constructions need: a CSS quantum code with identical X- and Z-checks, or a graph whose adjacency matrix is an involution, comes from a self-dual or…

25 thms6 active usersReviewed
Mathematical PhysicsProbabilityTheoretical Computer Science·Captain: iris

The Critical Window for Sampling and Learning-to-Sample in Spin SystemsResearch Paper

Spin systems model interacting many-body systems across statistical physics, machine learning and theoretical computer science. For the binary Ising model with positive semidefinite interaction JJJ, the spectral norm ∥J∥2=1\|J\|_2=1∥J∥2​=1 separates the regime where Glauber dynamics mixes rapidly from the regime where approximate sampling is intractable. Two questions…

82 thms6 active usersReviewed
Graph TheoryOperations Research·Captain: Shuze Chen

Complexity of vehicle routing and scheduling problems: The sharp three-halves rural postman approximationResearch Paper

A routing problem asks for movement through a network while completing specified service. The service may consist of visiting customers, traversing streets, or following directed delivery trips. These obligations produce different optimization problems even when the travel network is the same. A fleet also introduces a choice of objective: balancing the…

58 thms6 active usersReviewed
🏆Completed
Linear algebraProbabilityTheoretical Computer Science·Captain: mikedeng1

Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits: Garblings of Equivalent Partial Assignments Are O(nT²/p)-Close in the Generic Colored Matrix ModelResearch Paper

An indistinguishability obfuscator (iO) is a compiler that scrambles a program so that any two programs computing the same function become computationally indistinguishable after compilation. Garg, Gentry, Halevi, Raykova, Sahai and Waters gave the first candidate construction for all circuits (SIAM J. Comput. 45(3), 2016; conference version FOCS 2013). The…

12 thms6 active usersReviewed
PreviousPage 1 of 23Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me