Bibliographic record
Abstract
Parameterized complexity theory relaxes the classical notion of tractability and \nallows to solve some classically hard problems in a reasonably efficient way. However, many problems of interest remain intractable in the context of parameterized \ncomplexity. A completeness theory to categorize such problems has been developed \nbased on problems on circuits and Model Checking problems. Although a basic \nmachine characterization was proposed, it was not explored any further. \n \nWe develop a computational view of parameterized complexity theory based on \nresource-bounded programs that run on alternating random access machines. We \ndevelop both natural and normalized machine characterizations for the W[t] and \nL[t] classes. Based on the new characterizations, we derive the basic completeness results in parameterized complexity theory, from a computational perspective. Unlike the previous cases, our proofs follow the classical approach for showing basic NP-completeness results (Cook's Theorem, in particular). We give new proofs of the Normalization Theorem by showing that (i) the computation of a resource-bounded program on an alternating RAM can be represented by instances of corre- \nsponding basic parametric problems, and (ii) the basic parametric problems can be \ndecided by programs respecting the corresponding resource bounds. Many of the \nfundamental results follow as a consequence of our new proof of the Normalization \nTheorem. Based on a natural characterization of the W[t] classes, we develop new \nstructural results establishing relationships among the classes in the W-hierarchy, and the W[t] and L[t] classes. \nNontrivial upper-bound beyond the second level of the W-hierarchy is quite \nuncommon. We make use of the ability to implement natural algorithms to show \nnew upper bounds for several parametric problems. We show that Subset Sum, \nMaximal Irredundant Set, and Reachability Distance in Vector Addition Systems (Petri Nets) are in W[3], W[4], and W[5], respectively. In some cases, the new bounds result in new completeness results. We derive new lower bounds based on the normalized programs for the W[t] and L[t] classes. \nWe show that Longest Common Subsequence, with parameter the number of strings, is hard for L[t], t >= 1, and for W[SAT]. We also show that Precedence Constrained Multiprocessor Scheduling, with parameter the number of processors, is hard for L[t], t >= 1.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.003 | 0.027 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.003 |
| Bibliometrics | 0.002 | 0.003 |
| Science and technology studies | 0.002 | 0.008 |
| Scholarly communication | 0.006 | 0.018 |
| Open science | 0.003 | 0.006 |
| Research integrity | 0.002 | 0.007 |
| Insufficient payload (model declined to judge) | 0.010 | 0.001 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".