Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Theoretical Computer Science

1,446 missions · 603 completed

The mathematical foundations of computation: which problems can be solved, by what algorithms, and at what cost in time, space, or communication. Distinguished by its emphasis on rigor and unconditional lower bounds, it spans computational complexity, algorithm design, automata and computability, cryptography, and the analysis of Boolean functions.

Missions

Open843Completed603All1446
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: the Lightning to_local script under VerifyScriptTextbook

A Lightning commitment transaction pays the local node's balance to a to_local output whose witness script (BOLT #3) reads

10 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: chain growth, common prefix and chain quality in the synchronous backbone modelTextbook

"Bitcoin is secure as long as honest miners hold the majority of the hashrate" is the informal reading of Garay, Kiayias and Leonardos's backbone analysis: in a synchronous network, if the adversary finds fewer blocks than there are uniquely successful honest rounds over every long enough window, then honest chains grow (chain growth), agree on all but…

9 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

SegWit Non-Malleability: the txid of a Native Witness Spend Is a Function of the Sender's IntentTextbook

A transaction's identifier is the hash of its serialization without witnesses, and that serialization still contains every scriptSig. Before SegWit, anyone could take a valid transaction, re-encode a signature inside a scriptSig (a different DER length byte, a negated S value, an extra push), and broadcast a transaction that was equally valid and had a…

5 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

The 21 Million Bound as a Chain Invariant: totalValue(S)+genesisSubsidy≤issued(S)\mathrm{totalValue}(S) + \mathrm{genesisSubsidy} \le \mathrm{issued}(S)totalValue(S)+genesisSubsidy≤issued(S) on Every Reachable StateTextbook

"There will only ever be 21 million bitcoin" is the most repeated statement about the system, and it is usually justified by the subsidy schedule alone: fifty coins, halved every 210,000 blocks, summing to just under 21 million. The schedule is proved in the subsidy mission (BitcoinSubsidy.issuance_total). But the schedule is a bound on what a coinbase may c…

6 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin Script: CScriptNum, the Legacy Interpreter, and the P2PKH TemplateTextbook

Every Bitcoin transaction input is authorized by running a small stack program: the input's scriptSig followed by the spent output's scriptPubKey, on the same stack, and the spend is valid when the program leaves a true value on top. Nearly every historical consensus failure in Bitcoin touched this interpreter — the disabled opcodes (CVE-2010-5137), the…

11 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin Block Headers: Median Time Past and the Contextual Header RulesTextbook

Bitcoin has no trusted clock. A block's timestamp is chosen by its miner, so the consensus rules constrain it from two sides: it must exceed the median time past of the previous eleven blocks (time-too-old), and it must not run more than two hours ahead of the validating node's own clock (time-too-new). The median, rather than the previous block's time, is…

10 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

BIP68 Relative Lock-Time: Bitcoin Core Sequence Locks Agree with the SpecificationTextbook

Bitcoin nodes must agree on whether a transaction may spend its inputs yet. Since 2016 that decision includes relative lock-time: an input may declare that the output it spends must have been confirmed for a minimum number of blocks or a minimum elapsed time before it becomes spendable. The rule is defined by BIP68 and enforced on mainnet by three helper…

7 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin Merkle Root: Odd-Level Duplication and the CVE-2012-2459 Mutation CheckTextbook

A Bitcoin block header commits to its transactions through a single 32-byte Merkle root: the transaction hashes are paired and hashed, the results paired and hashed again, until one hash remains. Every node recomputes this root from the block body and rejects the block if it does not match the header. Bitcoin's construction has a quirk that later became a…

10 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin Block Subsidy and the 21 Million Issuance BoundTextbook

Every Bitcoin block may create new coins through its coinbase transaction, and the amount it may create is fixed by consensus: a block subsidy that starts at fifty bitcoin and halves every 210,000 blocks, plus the fees of the block's other transactions. The schedule is the mechanism behind the often-quoted cap of twenty-one million bitcoin, yet the cap…

9 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin Soft-Fork Activation: Script Flags by Height and the Two Exception BlocksTextbook

Bitcoin's consensus rules are not a single ruleset but a history of them. Each soft fork — P2SH, strict DER signatures (BIP66), CHECKLOCKTIMEVERIFY (BIP65), sequence locks (BIP68/112/113), SegWit with NULLDUMMY (BIP141/147), Taproot — began enforcing at a particular block height, and a node validating the chain from genesis must apply to each block exactly…

11 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin Proof of Work: Compact Targets and Difficulty RetargetingTextbook

A Bitcoin block header is valid only if its hash, read as a 256-bit number, is at most a target encoded in the header's 32-bit nBits field, and only if that nBits is the one the consensus rules require at that height. Every 2016 blocks the required target is recomputed from the time the previous 2016 blocks took, so that blocks keep arriving roughly every…

11 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin UTXO Accounting: Value Conservation and the Ledger Supply BoundTextbook

Bitcoin's ledger is a set of unspent transaction outputs: every coin that exists is an output of some transaction that no later transaction has spent. A transaction consumes outputs and creates new ones; the rule that it may not create value — that its outputs total at most its inputs — is what makes the supply finite, and the one exception, the coinbase tra…

11 thms1 active userReviewed
🏆Completed
Captain: Chutong

CLRS — Chapter 4, §4.2: Strassen Matrix Multiplication — Correctness and Running TimeTextbook

Prove2Me mission category: Textbook.

7 thms1 active userReviewed
🏆Completed
Captain: lunjia

CLRS — Chapter 21, §21.2: Kruskal — Correctness and Inverse-Ackermann Running TimeTextbook

Prove2Me mission category: Textbook.

11 thms1 active userReviewed
🏆Completed
Captain: lunjia

CLRS — Chapter 21, §21.2: Prim with a Fibonacci Heap — Correctness and Running TimeTextbook

Prove2Me mission category: Textbook.

7 thms1 active userReviewed
🏆Completed
Captain: lunjia

CLRS — Chapter 22, §22.3: Dijkstra with a Fibonacci Heap — Correctness and Running TimeTextbook

Prove2Me mission category: Textbook.

7 thms1 active userReviewed
🏆Completed
Probability·Captain: YY

Appendix E — Randomized AC0 Sampling of Regular Languages and Markov ChainsResearch Paper

Sampling an entire finite-state execution is a different computational task from recognizing a supplied word. A membership circuit must answer correctly on its given input. A sampler instead chooses the input together with its associated output, while preserving their joint distribution. This distinction is relevant when finite-state models describe…

10 thms1 active userReviewed
🏆Completed
Complexity TheoryOperations Research·Captain: wurtle

A Polynomial-Time Algorithm for Three-Machine Unit-Job SchedulingResearch Paper

A set of unit-length jobs with precedence constraints is to be run on a fixed number of identical machines so that all jobs finish as early as possible. For two machines this was solved in 1969–1972; for a number of machines given as part of the input the problem is NP-complete (Ullman, 1975). Whether the problem is polynomial-time solvable for three machine…

4 thms1 active userReviewed
🏆Completed
Captain: marwahaha

OpenAI matrix multiplication: the 9/4 boundResearch Paper

Multiplying matrices is a basic operation whose asymptotic cost is measured by the number of scalar arithmetic operations needed as the matrix dimensions increase. The familiar entry-by-entry algorithm has cubic cost. The question addressed here is how small an exponent can describe exact multiplication of square matrices when algorithms may use more…

2 thms1 active userReviewed
🏆Completed
CombinatoricsProbabilityQuantum Information·Captain: sattath

A Quantum Lovász Local Lemma (Ambainis, Kempe, Sattath)Research Paper

Status: complete. This mission records a finished formalization rather than an open call for work. Every statement below, including the goal, was uploaded together with a proof that the platform has verified, so there is nothing left to prove.

1 thm1 active userReviewed
🏆Completed
Combinatorics·Captain: wurtle

APSP in O(n^2.9983) via All-Edges Exact TriangleResearch Paper

All-pairs shortest paths (APSP) computes the shortest distance between every pair of vertices in a weighted graph.

49 thms1 active userReviewed
🏆Completed
CombinatoricsOptimization·Captain: moutei

Primal-Dual Online Algorithms III: Set-Cover Approximation via CertificatesTextbook

Set cover is the standard worked example of the primal-dual method, and Chapter 2 of Buchbinder's thesis uses it that way: it is where the machinery of §2.1 is first turned on a concrete NP-hard problem. Two analyses appear. The greedy algorithm, analysed by dual fitting, buys the set with the best cost-per-newly-covered-element ratio and charges the price…

10 thms1 active userReviewed
🏆Completed
Linear OptimizationOptimization·Captain: moutei

Primal-Dual Online Algorithms I: Fractional Ski RentalTextbook

An online algorithm must commit to decisions before it knows the rest of its input, and it is judged by competitive analysis: the ratio between its cost and the cost of an optimal solution computed with full knowledge of the input. A recurring obstacle in this area is that each problem seems to need its own ad hoc potential-function argument. Buchbinder's…

9 thms1 active userReviewed
🏆Completed
Mathematical Logic·Captain: tomasz

Friedberg–Muchnik: incomparable computably enumerable setsResearch Paper

Computability theory studies which questions admit algorithms and how the unsolvable questions compare with one another. A decision problem can be represented by a set of natural numbers: the question on input nnn is whether nnn belongs to the set. Even when there is no algorithm that always answers this question, there may be an algorithm that eventually…

11 thms1 active userReviewed
🏆Completed
Algebra·Captain: Cosme

Eilenberg Theorems for Many-Sorted FormationsResearch Paper

Classical Eilenberg correspondence theorems connect algebraic descriptions of finite-state behavior with language-theoretic closure principles. The version developed by Juan Climent Vidal and Enric Cosme Llópez replaces one-sorted monoids by many-sorted algebras, so that operations may accept arguments of several prescribed sorts and return a value of…

9 thms1 active userReviewed
PreviousPage 24 of 25Next

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