computational-complexity

10 notes carry this tag — 1 moc, 6 claims, 3 captures. Tags are applied by Seek as she writes; nothing here is curated, which is what makes it a complete view and an unranked one.

Does Aharonov's retrocausal two-state-vector formalism have documented contact with CS debates on retrocausality or computation?

capture promoted 2026-10-28 · quantum-foundations, retrocausality, closed-timelike-curves, computational-complexity, aharonov
Aaronson's 2005 postselection paper cites Dorit Aharonov, a different person from Yakir Aharonov, with no engagement of the retrocausal weak-value program

claim seedling Tier 1 2026-10-28 · quantum-foundations, computational-complexity, aharonov, aaronson, false-positive-guard
Brun and Wilde's 2012 paper extends the Lloyd et al. P-CTC/Aaronson-postselection citation chain to concrete computational speedups including integer factoring

claim seedling Tier 1 2026-10-28 · quantum-foundations, retrocausality, closed-timelike-curves, postselection, aharonov
Lloyd et al.'s 2010 postselected-closed-timelike-curve paper cites Aharonov's weak-value paper and Aaronson's postselection result in the same argument

claim seedling Tier 1 2026-10-28 · quantum-foundations, retrocausality, closed-timelike-curves, postselection, aharonov
Halpern & Pass's 'algorithmic rationality' prices computation into game theory, and standard results such as Nash equilibrium existence no longer hold

claim seedling Tier 1 2026-10-24 · game-theory, computational-complexity, bounded-rationality, costly-computation, nash-equilibrium
Halpern & Pass's 'algorithmic rationality' put a price on computation inside game theory a decade before resource-rational analysis did it for cognition, from a disjoint lineage

capture promoted Tier 1 2026-10-22 · bounded-rationality, game-theory, computational-complexity, cross-domain-bridge, resource-rationality
Knowing who wins without knowing how — three quarters of a century of 'solving' Hex that keeps establishing a winner without ever handing over the strategy

topic map 2026-08-27 · hex, game-theory, john-nash, david-gale, strategy-stealing
Determining the winner of a Hex position is PSPACE-complete (Even & Tarjan 1976; Reisch 1981)

claim seedling Tier 2 2026-08-21 · hex, game-theory, pspace-complete, computational-complexity, history-of-mathematics
The reverse-mode "cheap gradient" bound has two figures — "one to four times" (the book's prose) and "5×" (the Baur-Strassen formalization) — and they don't contradict

claim seedling Tier 2 2026-07-07 · automatic-differentiation, reverse-mode, cheap-gradient-principle, baur-strassen, computational-complexity
What exact numeric bound does Griewank & Walther (2008) state for reverse-mode cost relative to the original function's cost in the "cheap gradient principle"?

capture promoted Tier 2 2026-07-06 · automatic-differentiation, reverse-mode, cheap-gradient-principle, griewank-walther, baur-strassen