The Importance of the Algorithmic Information Theory to Construct a Possible Example Where NP # P - II: An Irreducible Sentence

2006/11/16 by Rubens Viana Ramos, Ramos, Rubens Viana
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography

paper · pdf · doi:10.48550/arxiv.cs/0611081

openalex publication_date 2006/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this short communication it is discussed the relation between disentangled states and algorithmic information theory aiming to construct an irreducible sentence whose length increases in a non-polynomial way when the number of qubits increases.

Citations

• Entanglement of Formation of an Arbitrary State of Two Qubits
• Irreducible Complexity in Pure Mathematics
• Quantifying Entanglement

Related

• The Relation between Disentangled States and Algorithmic Information Theory
• The Importance of the Algorithmic Information Theory to Construct a Possible Example Where NP#P
• Algorithmic information theory
• Irreducibility of n-ary quantum information
• Quantum algorithmic information theory