Research map / Learning theory and algorithms / Combinatorial and search optimization
Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce one-sided constraints to Directed Subset Feedback Arc Set | ALMOSTCSP(S≥) · One-sided STP relations | parameterized complexity: in FPT | Helped |
| Use iterative compression with an Edge Multicut subroutine | ALMOSTCSP(S=) · Equation STP relations | parameterized complexity: in FPT | Helped |
| Restrict the constraint language to relations containing (0, 0) | ALMOSTCSP(A) · A ⊆ S0 | classical complexity: constant-time solvable | Helped |
| Allow non-trivial one-sided relations | ALMOSTCSP(A) · One-sided STP fragments | parameterized complexity: NP-hard; in FPT | Mixed |
| Allow non-zero equation relations | ALMOSTCSP(A) · Equation STP fragments | parameterized complexity: NP-hard; in FPT | Mixed |
| Use any other non-trivial fragment beyond the one-sided and equation cases | ALMOSTCSP(A) · Remaining STP fragments | parameterized complexity: W[1]-hard | Hurt |
Closest papers by meaning
- Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs (ICML 2026 · similarity 0.85)
- Boosting Inference with Guided Reasoning: Stochastic Exploration for Recursive Models (NeurIPS 2026 · similarity 0.85)
- A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.84)
- Think Smarter not Harder: Adaptive Reasoning with Inference Aware Optimization (ICML 2025 · similarity 0.83)
- Atom of Thoughts for Markov LLM Test-Time Scaling (NeurIPS 2025 · similarity 0.83)
- Beyond What Seems Necessary: Hidden Gains from Scaling Training-Time Reasoning Length under Outcome Supervision (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.