Elamur Research⌕
☰
home / papers / 2026 / NP-Hard Lower Bound Complexity for Semantic Self-Verification

NP-Hard Lower Bound Complexity for Semantic Self-Verification

Paper · 2026 · Robin Young

Summary

The paper asks how computationally hard it is for an AI system to confirm that it has understood the rules meant to govern it, as in constitutional AI or instruction-following setups. Young formalizes this as Semantic Self-Verification (SSV). An instance is a statement plus a semantic framework. The framework contains ambiguous terms, each with two candidate senses, and constraints restricting which sense combinations are allowed. The statement claims that some admissible reading of its own terms exists, and SSV asks whether that claim is true. The work is purely theoretical and uses no data. Its core result is a polynomial-time reduction from 3-SAT: variables become terms, truth values become sense choices, and clauses become semantic constraints. This shows SSV is NP-complete even in this stripped-down form. The author argues that richer, more realistic semantics can only raise the difficulty. Consequently, practical alignment methods must rely on approximation and external oversight. A system that answers very fast cannot be performing exhaustive verification in the worst case.

Key points

  • The framework is defined as F = (T, Σ, Cons, M, V): terms, binary senses per term, constraints, the set of 2^n possible interpretations, and a function checking constraint satisfaction.
  • An illustrative example maps the principles "helpful", "honest" and "privacy" to two readings each. These readings are linked by mutual implication constraints.
  • Moving from binary to k-way meanings keeps the lower bound, since such choices can be encoded with ⌈log₂ k⌉ binary variables. Continuous meaning spaces push the problem toward SMT-style reasoning.
  • The author conjectures that recursive, context-dependent or quantified constraints (resembling QBF) make enriched SSV PSPACE-hard. This is not proven.
  • The paper rejects average-case optimism for safety, pointing to adversarial jailbreaking as a hunt for worst-case instances. It appeared at EACL 2026 (Long Papers, pp. 1304–1318).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksSocial Sciences · 1,954 worksSafety Research · 626 worksComputational Theory and Mathematics · 321 works

Cite

Cite as Robin Young. 2026. NP-Hard Lower Bound Complexity for Semantic Self-Verification. Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.eacl-long.60

@inproceedings{young2026np,
  title = {{NP-Hard Lower Bound Complexity for Semantic Self-Verification}},
  author = {Robin Young},
  booktitle = {Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.eacl-long.60},
  url = {https://doi.org/10.18653/v1/2026.eacl-long.60}
}

References

37 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Michael Anderson and Susan Leigh Anderson, editors. 2011. Machine Ethics. Cambridge Univ. Press. find
  2. Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova Dassarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, John Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodds, Danny Hernandez, Tristan Hume, and 12 others. 2022a.… find
  3. Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, John Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Chris Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, E Perez, and 32 others. 2022b. Constitu…
  4. Emily M. Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell. 2021. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’21, page 610–623, New York, NY, USA. Associat… find
  5. Emily M. Bender and Alexander Koller. 2020. Climbing towards nlu: On meaning, form, and understanding in the age of data. In Annual Meeting of the Association for Computational Linguistics.
  6. Sam Bowman, Jeeyoon Hyun, Ethan Perez, Edwin Chen, Craig Pettit, Scott Heiner, Kamile Lukosiute, Amanda Askell, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Chris Olah, Daniela Amodei, Dario Amodei, Dawn Drain, Dustin Li, Eli Tran-Johnson, and 27 others. 2022. Measuring p…
  7. Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras. 2024. Scalable AI safety via doubly-efficient debate. In Forty-first International Conference on Machine Learning. find
  8. Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang. 2023. Sparks of artificial general intelligence: Early experiments with gpt-4. Preprint, a…
  9. Ryan Carey and Tom Everitt. 2023. Human control: definitions and algorithms. In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, UAI ’23. JMLR.org. find
  10. Noam Chomsky. 1957. Syntactic Structures. Mouton and Co., The Hague. find
  11. Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017. Deep reinforcement learning from human preferences. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 4302–4310, Red Hook, NY, USA. Curran Associa… find
  12. Alessandro Cimatti, Alberto Griggio, Ahmed Irfan, Marco Roveri, and Roberto Sebastiani. 2018. Incremental linearization for satisfiability and verification modulo nonlinear arithmetic and transcendental functions. ACM Transactions on Computational Logic (TOCL), 19:1 – 52. find
  13. Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC ’71, page 151–158, New York, NY, USA. Association for Computing Machinery. find
  14. Abram Demski and Scott Garrabrant. 2020. Embedded agency. Preprint, arXiv:1902.09469. — [arXiv:1902.09469](https://arxiv.org/abs/1902.09469) find
  15. Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, and 6 others. 2021. A mathe… find
  16. Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA. find
  17. Dylan Hadfield-Menell, Anca Dragan, Pieter Abbeel, and Stuart Russell. 2016. Cooperative inverse reinforcement learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, page 3916–3924, Red Hook, NY, USA. Curran Associates Inc. find
  18. Stevan Harnad. 1990. The symbol grounding problem. Physica D: Nonlinear Phenomena, 42(1-3):335–346. find
  19. Dan Hendrycks, Collin Burns, Steven Basart, Andrew Critch, Jerry Li, Dawn Song, and Jacob Steinhardt. 2021. Aligning {ai} with shared human values. In International Conference on Learning Representations.
  20. Dan Hendrycks, Kimin Lee, and Mantas Mazeika. 2019. Using pre-training can improve model robustness and uncertainty. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2712–2721. PMLR. find
  21. Geoffrey Irving, Paul Francis Christiano, and Dario Amodei. 2018. Ai safety via debate. ArXiv, abs/1805.00899.
  22. Jiaming Ji, Tianyi Qiu, Boyuan Chen, Borong Zhang, Hantao Lou, Kaile Wang, Yawen Duan, Zhonghao He, Lukas Vierling, Donghai Hong, Jiayi Zhou, Zhaowei Zhang, Fanzhi Zeng, Juntao Dai, Xuehai Pan, Kwan Yee Ng, Aidan O’Gara, Hua Xu, Brian Tse, and 7 others. 2025. Ai alignment: A comprehensive survey. Pr…
  23. Guy Katz, Clark W. Barrett, David L. Dill, Kyle D. Julian, and Mykel J. Kochenderfer. 2017. Reluplex: An efficient smt solver for verifying deep neural networks. ArXiv, abs/1702.01135. — [arXiv:1702.01135](https://arxiv.org/abs/1702.01135) find
  24. Victoria Krakovna, Laurent Orseau, Miljan Martic, and Shane Legg. 2018. Penalizing side effects using stepwise relative reachability. arXiv: Learning. find
  25. Harrison Lee, Samrat Phatale, Hassan Mansoor, Thomas Mesnard, Johan Ferret, Kellie Lu, Colton Bishop, Ethan Hall, Victor Carbune, Abhinav Rastogi, and Sushant Prakash. 2024. Rlaif vs. rlhf: scaling reinforcement learning from human feedback with ai feedback. In Proceedings of the 41st International… find
  26. Changliu Liu, Tomer Arnon, Christopher Lazarus, Clark W. Barrett, and Mykel J. Kochenderfer. 2019. Algorithms for verifying deep neural networks. Found. Trends Optim., 4:244–404. find
  27. Melanie Mitchell. 2021. Why ai is harder than we think. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’21, page 3, New York, NY, USA. Association for Computing Machinery. find
  28. Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. 2020. Zoom in: An introduction to circuits. Distill. Https://distill.pub/2020/circuits/zoom-in. find
  29. Chris Olah, Arvind Satyanarayan, Ian Johnson, Shan Carter, Ludwig Schubert, Katherine Ye, and Alexander Mordvintsev. 2018. The building blocks of interpretability. Distill. Https://distill.pub/2018/building-blocks. find
  30. Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022. Train…
  31. Christos H. Papadimitriou and Mihalis Yannakakis. 1982. The complexity of facets (and some facets of complexity). In Symposium on the Theory of Computing. find
  32. Ethan Perez, Saffron Huang, Francis Song, Trevor Cai, Roman Ring, John Aslanides, Amelia Glaese, Nat McAleese, and Geoffrey Irving. 2022. Red teaming language models with language models. In Conference on Empirical Methods in Natural Language Processing.
  33. A First, we restate the SSV problem formulation. This is the same as the formalization in the main body of the paper, available here again for reference. Problem 3 (Semantic Self-Verification (SSV)). • Input: Stuart J. Russell. 2019. Human Compatible: Artificial Intelligence and the Problem of Contr… find
  34. Sanjit A. Seshia, Dorsa Sadigh, and S. Shankar Sastry. 2022. Toward verified artificial intelligence. Commun. ACM, 65(7):46–55. find
  35. Chelsea Sidrane, Amir Maleki, Ahmed Irfan, and Mykel J. Kochenderfer. 2022. Overt: an algorithm for safety verification of neural network control policies for nonlinear systems. J. Mach. Learn. Res., 23(1). find
  36. Nate Soares and Benya Fallenstein. 2017. Agent foundations for aligning machine intelligence with human interests: A technical research agenda. Technical report, Machine Intelligence Research Institute. find
  37. Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. 2020. Learning to summarize from human feedback. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY, US… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/young-2026-np-hard-lower-bound-complexity/