tTA Spectral Approach to #P -Hardness via Clause Expander…
2 reactions
tTA Spectral Approach to #P -Hardness via Clause Expander Graphs?
I believe to have proven it what I set out for, though it's now technically a Laplacian-energy approach via clause expander graphs. No notation changes. I initially proposed the problem on the P vs NP board and now believe to have found a solution. The problem it is addressing: \\textbf{Input.}
A finite weighted graph \\(E=(V,\\mathcal{E},w)\\)
whose edge weights \\(w:\\mathcal{E}\\to\\{1,\\dots,108\\}\\) are written in unary,
together with a vertex–type map
\\(\\ell:V\\to\\Sigma=\\{\\mathrm{VAR},\\mathrm{GAD},\\mathrm{ANC}\\}\\).
\\textbf{Task.}
Let \\(k:=\\bigl|\\{v\\in V:\\ell(v)=\\mathrm{VAR}\\}\\bigr|\\).
Compute
\\\
\\Lambda\\text{-}\\mathrm{Sum}(E)\\;:=\\;
\\sum\_{x\\in\\{0,1\\}\^{n}}
\\widehat{\\Lambda}\_{E}(x),
\\\]
where \\(\\widehat{\\Lambda}\_{E}(x)\\) is the global‑clip functional
defined in Eq. 7.1.
Results:
In our first approach, we attempted to create a 'one-shot' gadget where each unsatisfying assignment contributes exactly 4. We prove this impossible (Theorem 6.1), leading us to an additive scheme where contributions scale with violated clauses. Post-processing recovers the counting property. We define a Laplacian-energy sum, then show that approximating this spectral sum even within an additive error of ±1 is #P -hard.he key details begin in Section 6 and culminate with the main result in 8.2, hough it might help to skim what comes before to get a sense of the approach. The novelty is in connecting spectral graph properties directly to counting complexity through a new gadget construction.
I'd appreciate any feedback! 😁
Here's a link to the paper: [https://doi.org/10.5281/zenodo.15668482 https://doi.org/10.5281/zenodo.15668482
The most updated version of the paper will now better reflect what became of each appraoch.
#technology
I believe to have proven it what I set out for, though it's now technically a Laplacian-energy approach via clause expander graphs. No notation changes. I initially proposed the problem on the P vs NP board and now believe to have found a solution. The problem it is addressing: \\textbf{Input.}
A finite weighted graph \\(E=(V,\\mathcal{E},w)\\)
whose edge weights \\(w:\\mathcal{E}\\to\\{1,\\dots,108\\}\\) are written in unary,
together with a vertex–type map
\\(\\ell:V\\to\\Sigma=\\{\\mathrm{VAR},\\mathrm{GAD},\\mathrm{ANC}\\}\\).
\\textbf{Task.}
Let \\(k:=\\bigl|\\{v\\in V:\\ell(v)=\\mathrm{VAR}\\}\\bigr|\\).
Compute
\\\
\\Lambda\\text{-}\\mathrm{Sum}(E)\\;:=\\;
\\sum\_{x\\in\\{0,1\\}\^{n}}
\\widehat{\\Lambda}\_{E}(x),
\\\]
where \\(\\widehat{\\Lambda}\_{E}(x)\\) is the global‑clip functional
defined in Eq. 7.1.
Results:
In our first approach, we attempted to create a 'one-shot' gadget where each unsatisfying assignment contributes exactly 4. We prove this impossible (Theorem 6.1), leading us to an additive scheme where contributions scale with violated clauses. Post-processing recovers the counting property. We define a Laplacian-energy sum, then show that approximating this spectral sum even within an additive error of ±1 is #P -hard.he key details begin in Section 6 and culminate with the main result in 8.2, hough it might help to skim what comes before to get a sense of the approach. The novelty is in connecting spectral graph properties directly to counting complexity through a new gadget construction.
I'd appreciate any feedback! 😁
Here's a link to the paper: [https://doi.org/10.5281/zenodo.15668482 https://doi.org/10.5281/zenodo.15668482
The most updated version of the paper will now better reflect what became of each appraoch.
#technology
2
| 9,000 mlx | |
| 14 | |
| 2 |