An f(k) n^O(1) algorithm for #k-matching is claimed, implying #W[1] = FPT and falsifying ETH, #ETH, and W[1] ≠ FPT.
In: Proceedings of the Third Annual ACM Symposium
9 Pith papers cite this work. Polarity classification is still indexing.
9
Pith papers citing it
representative citing papers
Deciding DFA primality is NP-hard, established by reduction from propositional satisfiability using a characterization of primality for a relevant class of automata.
LLMEval-Logic is a solver-verified Chinese logical reasoning benchmark with 246 base and 190 hard items that shows frontier LLMs reach only 37.5% hard-item accuracy and 60.16% joint formalization score.
Bounded fitting can be extended to expressive description logics while retaining generalization guarantees and implemented practically via SAT solvers.
Multi-token prediction induces a two-stage reverse reasoning process in Transformers via gradient decoupling, improving planning on synthetic and realistic tasks.
Satisfiability of propositional logic with nonemptiness atom NE in team semantics is NP-complete, validity coNP-complete, and model checking polynomial-time.
Model-checking stateless quantum pushdown systems against PCTL is undecidable while against bPCTL it is decidable and NP-hard.
A compact QUBO encoding derived via ILP reduces logical variables by thousands in AES, MD5, SHA1 and SHA256, with over 8x reduction for AES-256.
citing papers explorer
-
$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
An f(k) n^O(1) algorithm for #k-matching is claimed, implying #W[1] = FPT and falsifying ETH, #ETH, and W[1] ≠ FPT.
-
Deciding DFA-Primality is NP-Hard
Deciding DFA primality is NP-hard, established by reduction from propositional satisfiability using a characterization of primality for a relevant class of automata.
-
LLMEval-Logic: A Solver-Verified Chinese Benchmark for Logical Reasoning of LLMs with Adversarial Hardening
LLMEval-Logic is a solver-verified Chinese logical reasoning benchmark with 246 base and 190 hard items that shows frontier LLMs reach only 37.5% hard-item accuracy and 60.16% joint formalization score.
-
Bounded Fitting for Expressive Description Logics
Bounded fitting can be extended to expressive description logics while retaining generalization guarantees and implemented practically via SAT solvers.
-
How Transformers Learn to Plan via Multi-Token Prediction
Multi-token prediction induces a two-stage reverse reasoning process in Transformers via gradient decoupling, improving planning on synthetic and realistic tasks.
-
Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
Satisfiability of propositional logic with nonemptiness atom NE in team semantics is NP-complete, validity coNP-complete, and model checking polynomial-time.
-
Computational Complexity of Model-Checking Quantum Pushdown Systems
Model-checking stateless quantum pushdown systems against PCTL is undecidable while against bPCTL it is decidable and NP-hard.
-
A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions
A compact QUBO encoding derived via ILP reduces logical variables by thousands in AES, MD5, SHA1 and SHA256, with over 8x reduction for AES-256.
- Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization