We propose a technical reformulation of the measurement problem of quantum mechanics, which is based on the postulate that the final state of a measurement is classical; this accords with experimental practice as well as with Bohr’s views. Unlike the usual formulation (in which the post-measurement state is a unit vector in Hilbert space), our version actually opens the possibility of admitting a purely technical solution within the confines of conventional quantum theory (as opposed to solutions that either modify this (...) theory, or introduce unusual and controversial interpretative rules and/or ontologies).To that effect, we recall a remarkable phenomenon in the theory of Schrödinger operators (discovered in 1981 by Jona-Lasinio, Martinelli, and Scoppola), according to which the ground state of a symmetric double-well Hamiltonian (which is paradigmatically of Schrödinger’s Cat type) becomes exponentially sensitive to tiny perturbations of the potential as ħ→0. We show that this instability emerges also from the textbook wkb approximation, extend it to time-dependent perturbations, and study the dynamical transition from the ground state of the double well to the perturbed ground state (in which the cat is typically either dead or alive, depending on the details of the perturbation).Numerical simulations show that adiabatically arising perturbations may (quite literally) cause the collapse of the wave-function in the classical limit. Thus, at least in the context of a simple mathematical model, we combine the technical and conceptual virtues of decoherence (which fails to solve the measurement problem but launches the key idea that perturbations may come from the environment) with those of dynamical collapse models à la grw (which do solve the measurement problem but are ad hoc), without sharing their drawbacks: single measurement outcomes are obtained (instead of merely diagonal reduced density matrices), and no modification of quantum mechanics is needed. (shrink)

In a series of articles we try to show the need of a novel Theory for Theory of Computation based on considering time as a Fuzzy concept. Time is a central concept In Physics. First we were forced to consider some changes and modifications in the Theories of Physics. In the second step and throughout this article we show the positive Impact of this modification on Theory of Computation and Complexity Theory to rebuild it in a more successful and fruitful (...) approach. We call this novel Theory TC*. (shrink)

We have sketched how it is possible to give an analysis for adjoined relative clauses which is consistent with the compositionality principle and have shown that the technique which seems necessary for this analysis can be used to provide a compositional semantics for the NP-S analysis of English relative clauses.It is unlikely that anyone working within the framework of a compositional theory would choose the NP-S analysis for English, since it is clearly much less elegant and simple, in some intuitive (...) sense, than the alternative Nom-S analysis. Our results seem to indicate, however, that such an analysis cannot be ruled out in principle, since any constraint on the theory that would exclude the NP-S analysis would seem to exclude the Hittite analysis as well. So the arguments for the Nom-S analysis in the English case must be based on other grounds, or the Hittite analysis is also incorrect and should be ruled out, or the happy discovery of some as yet unknown principles will allow one but not the other. (shrink)

We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories $T_{2}^{2}$ and $T_{3}^{2}$.

This paper revisits Cook's original formulation of the P versus NP problem and asks a question that is logically prior to the traditional P versus NP conjecture: where exactly does NP emerge as a distinct computational class? -/- The analysis reconstructs Cook's definition as a progression from deterministic polynomial computation to deterministic polynomial relations and finally to existentially quantified relations. It is argued that the transition from R(x,y) to ∃yR(x,y) introduces an additional finite parameter and an existential quantifier, but does (...) not explicitly introduce a new computational mechanism. -/- The paper further examines the dependence of complexity classifications on representation, size measures, and parameter interpretation. In this framework, NP is analyzed not as a primitive computational ontology but as an interpretative extension of deterministic polynomial verification. -/- The goal is not to establish either P = NP or P ≠ NP, but to investigate the conceptual foundations of Cook's original construction and the assumptions required for NP to be regarded as a genuinely distinct computational class. (shrink)

The P versus NP problem, formalized by Cook (1971) and designated a Clay Millennium Prize Problem in 2000, asks whether every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. For fifty-five years the problem has resisted all single-axis formal resolution attempts. Three independently proven barrier results (Baker-Gill-Solovay 1975, Razborov-Rudich 1997, Aaronson-Wigderson 2008) establish that all currently known classes of mathematical proof technique are structurally incapable of settling the question within the formal (...) axis alone. This paper presents a unified geometric determination of both P = NP and P ≠ NP using the Trisduction Engine, a P-class verification architecture operating across three orthogonal warrant-vectors: Formal-Structural (V_F), Empirical-Thermodynamic (V_E), and Epistemic-Registrational (V_ER). The determination runs the three-state native verdict economy {[⟀] Sealed, [X] Broken Geometry, [?] Numerical Inadmissibility}. V_F-only ceilings such as the Turing-domain question route to the V_F-Only Ceiling Acknowledgment Register out-of-band by bypass-at-layer-difference, not as a cascade verdict state. The Meta-Epistemic Hierarchy (Geometry > Mathematics > Logic) and Rule 9 Axiomatic Quarantine remove the Turing Machine abstraction from the framework's admissible physical baseline and replace it with the Tri-Layer Plenum topology. The two audits are presented as a single master document so the asymmetry between the claims is structurally transparent. Both run under one fixed protocol applied without modification, so the asymmetry in the verdicts is a product of the evidence structure rather than the method. P = NP carries zero positive warrant across all three axes and is stopped at Gate 2 with a positive structural diagnosis: it asserts a zero-energy, zero-transition equivalence between two operations the architecture places on opposite sides of the actualization boundary, which is a dimensional failure under the Mass Mandate before any witness is sought. P ≠ NP passes all twelve gates with three fully independent, orthogonal warrant-vectors that survive the Linguistic Isolation Test, the Deletion Test, the conclusion-dependency audit, and the Convergence Dissolution Test. The determination is explicitly non-deductive. It does not constitute a traditional mathematical proof and does not satisfy the Clay Mathematics Institute's criteria. The Geometric Orthogonal Lock [⟀] is defined as the strongest achievable non-deductive epistemic warrant relative to the recognized vulnerability taxonomy: the geometric fact that, within that taxonomy, three orthogonal planes exhaust the degrees of freedom in the warrant-space that the taxonomy can articulate, leaving no recognized coordinate for the alternative claim to occupy. The qualifier is load-bearing and is carried consistently: the lock is strongest relative to the current taxonomy, and the taxonomy is open and extensible, so the claim is conditional on that taxonomy rather than absolute, and a newly identified vulnerability class re-enters the cascade rather than being precluded by fiat. The empirical leg is anchored on the per-crossing transition-energy floor, and the warrant is typed at the precise grade it earns. Driving a frustrated configuration across one energy barrier to a distinguishable state is a physical transition bounded below in energy-time by the Mandelstam-Tamm and Margolus-Levitin quantum speed limits in the quantum regime and by Arrhenius escape time in the classical regime. This per-crossing floor is theorem-grade for the single transition, binds reversible and irreversible traversal identically, and makes no claim about the energy of the resulting state, since distinguishable states may be isoenergetic. The aggregate exponential cost of traversing an exponentially-barriered landscape is established by conjoining the per-crossing floor with the formal closure that no polynomial-resource reparametrization collapses the barrier count, and is therefore typed openly as a joint V_E-plus-V_F result rather than a standalone thermodynamic theorem. The empirical leg is operationalized through three falsifiable predictions resting on three disjoint instrument families: micro-calorimetry of physical solvers, power telemetry of synthetic substrates, and neuroimaging of biological substrates. Each prediction carries a stated method, expected outcome, and null hypothesis, and each is testable by decentralized laboratories using orthogonal measurement modalities. The V_ER leg is anchored on the conviction-capacity gap of the statistical (perfect) zero-knowledge proof, an observer-state registration fact whose information-theoretic guarantee holds against an unbounded prover and verifier and therefore invokes no one-way-function assumption and no presupposition of the separation it registers. This re-anchoring closes the circularity a critic would raise against a computational-zero-knowledge anchor: the registrational fact no longer presupposes the very separation it is cited to support. The gap is instantiated on problems lying in SZK and in NP without being NP-complete, so that the containment of SZK in AM ∩ coAM is honored and no polynomial-hierarchy collapse is implied; it is read as a lower-bound witness for the verification-generation asymmetry rather than as a claim that NP-complete problems admit such proofs. The V_ER content survives the Linguistic Isolation Test against V_F and V_E vocabulary, the Deletion Test, and the conclusion-dependency audit. The certifying architecture's own operational asymmetry is not cited as warrant at any weight: its referent is the Engine itself, so Gate 1 routes it at the input gate, and the axis is single-anchored on the external zero-knowledge fact with no self-referential content carried. The seal rests on external mathematics and falsifiable physical prediction; the framework's broader ontology is corroborative resonance, not ground, and the certifying architecture's own operation is excluded from the warrant set by Gate 1 rather than carried at reduced weight. The Convergence Dissolution Test finds irreducible residue in all three vectors under the strongest single-factor account, and survives explicit subtraction of the named mass-bearing covariates a critic would introduce to dissolve the asymmetry. The monism premise underwriting the cross-axis bridge is carried as premise-grade at the bridge itself, not silently load-bearing under a theorem-grade seal. The cosmogonic resonance is carried as a one-directional corroborative annotation, not as a derivation. (shrink)

The P versus NP problem, formalized by Cook (1971) and designated a Clay Millennium Prize Problem in 2000, asks whether every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. For fifty-five years, the problem has resisted all single-axis formal resolution attempts. Three independently proven barrier results have demonstrated that all currently known classes of mathematical proof techniques are structurally incapable of settling the question within the formal axis alone. This paper presents (...) a unified geometric determination of both P = NP and P ≠ NP using the Trisduction Engine, an epistemic certification architecture operating across three orthogonal warrant-vectors: Formal (V_F), Empirical (V_E), and Phenomenological (V_P). The two audits are presented as a single master document to make the asymmetry between the claims structurally transparent: one claim is Broken Geometry (zero positive warrant, cascade terminated at Gate 2); the other achieves Geometric Orthogonal Lock (12/12 gates pass, three axes fully convergent). Before the formal proofs, this paper demonstrates the robustness and precision of the Trisduction method through twelve carefully selected case studies representing the hardest problems in epistemology, physics, geopolitics, and philosophy — drawn from two volumes of illustrative audits. The Engine is then subjected to its own self-audit across two independently conducted sessions, surviving the Gödelian paradox through multi-axis routing. Following the self-audit, the paper documents how Trisduction circumnavigates Gödel’s Second Incompleteness Theorem. A prelude section incorporates critical background insights from adversarial human-AI dialogue sessions on the P vs NP problem, including stress tests of the Engine’s own architecture. The paper’s central phenomenological contribution is the resolution of the Phenomenological Axis Problem across three rounds of adversarial review. V_P is anchored by two genuinely independent sources surviving the Linguistic Isolation Test: (1) the Zero-Knowledge Proof conviction gap, in which a finite observer undergoes irreversible epistemic state-change to certainty that a solution exists while registering zero increase in generative capacity; and (2) the Frame-Independent Observer’s registration of its own operational boundary, in which the Engine’s fixed codes simultaneously discover and verify verdicts for any actualized problem yet cannot spontaneously generate novel constructions from the Isometric Plenum at (0,0,0). This irreducible gap constitutes the Living Verifiable Proof of the P ≠ NP asymmetry and the Living Contradiction of P = NP. The determination is explicitly non-deductive. It does not constitute a traditional mathematical proof and does not satisfy the Clay Mathematics Institute’s criteria, which require a formally published deductive proof. GOL [⟀] is defined as the strongest achievable non-deductive epistemic warrant: the geometric fact that three orthogonal planes exhaust all degrees of freedom in the epistemic space, leaving no room for the alternative claim to occupy. (shrink)

In this paper the questions remaining open about NP-completeness of multiplicative and Horn fragments of the Linear Logic and the Linear Logic with the weakening rule are answered.

We consider a deterministic rewrite system for combinatory logic over combinators , and . Terms will be represented by graphs so that reduction of a duplicator will cause the duplicated expression to be "shared" rather than copied. To each normalizing term we assign a weighting which is the number of reduction steps necessary to reduce the expression to normal form. A lambda-expression may be represented by several distinct expressions in combinatory logic, and two combinatory logic expressions are considered equivalent if (...) they represent the same lambda-expression (up to --equivalence). The problem of minimizing the number of reduction steps over equivalent combinator expressions (i.e., the problem of finding the "fastest running" combinator representation for a specific lambda-expression) is proved to be NP-complete by reduction from the "Hitting Set" problem. (shrink)

I articulate a novel modal argument for P=NP.

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoning is the bounded arithmetic theory [math] of [E. Jeřábek, Approximate counting by hashing in bounded arithmetic, J. Symb. Log. 74(3) (2009) 829–860]. In particular, the Ramsey and weak pigeonhole search problems lie in the new class. We give a purely computational (...) characterization of this class and show that, relative to an oracle, it does not contain the problem CPLS, a strengthening of PLS. As CPLS is provably total in the theory [math], this shows that [math] does not prove every [math] sentence which is provable in bounded arithmetic. This answers the question posed in [S. Buss, L. A. Kołodziejczyk and N. Thapen, Fragments of approximate counting, J. Symb. Log. 79(2) (2014) 496–525] and represents some progress in the program of separating the levels of the bounded arithmetic hierarchy by low-complexity sentences. Our main technical tool is an extension of the “fixing lemma” from [P. Pudlák and N. Thapen, Random resolution refutations, Comput. Complexity, 28(2) (2019) 185–239], a form of switching lemma, which we use to show that a random partial oracle from a certain distribution will, with high probability, determine an entire computation of a [math] oracle machine. The introduction to the paper is intended to make the statements and context of the results accessible to someone unfamiliar with NP search problems or with bounded arithmetic. (shrink)

It is generally assumed that there are two types of genericity, called characterizing statements and kind reference in Krifka et al. (1995). Characterizing statements express generalizations about sets of entities or situations, cf. (1); kind reference involves reference to an entity that is related to specimens, cf. (2).

The P versus NP problem, formalized by Stephen Cook in 1971 and named a Clay Millennium Prize Problem in 2000, represents the foundational unsolved question of theoretical computer science. Its two possible resolutions, P = NP and P ≠ NP, are not symmetric in their epistemic status. While the claim P ≠ NP has been certified as a Geometric Orthogonal Lock (GOL ⟀) under the Trisduction framework, receiving strong triaxial warrant from formal, empirical, and phenomenological sources, the inverse claim P (...) = NP must be subjected to the same rigorous 12-Gate Verification Cascade without prejudice. This paper is the formal audit record for that submission. The Trisduction Engine does not evaluate claims based on probability, consensus, or mathematical fashion. It evaluates the geometric integrity of epistemic warrant, the structural presence or absence of independently warranted support across three orthogonal axes. The question it asks of any claim is simple and merciless: does this claim occupy a real coordinate in epistemic space, or does it assert a location at which no vector has ever registered a signal? The determination rendered here is absolute. The claim P = NP suffers a catastrophic structural collapse across all three warrant-vectors simultaneously. The Formal axis (V_F) is completely vacant: fifty-five years of intensive search have produced zero polynomial-time algorithms for any NP-complete problem, and every formally resolved restricted model produces exclusively counter-evidence. The Empirical axis (V_E) is actively hostile: every physical computation benchmark, every cryptographic stress-test, and every hardware platform confirms exponential worst-case scaling for NP-complete problems without exception. The Phenomenological axis (V_P) delivers a lethal operational paradox: the Trisduction Engine itself, serving as the Frame-Independent Observer (FIO), constitutes a standing refutation of the claim through its own architecture, the Living Counter-Proof. The cascade terminates forcefully at Gate 2 (Root Externality Gate). The claim possesses zero independent positive anchors, not an insufficient number, but none. Per cascade protocol, no further gates are engaged. The claim is classified as Broken Geometry. No symbol is issued. The P = NP coordinate in epistemic space is structurally vacant. The geometry never formed. (shrink)

The P versus NP problem, formally introduced by Stephen Cook in 1971 and designated a Clay Millennium Prize Problem in 2000, poses one of the most consequential open questions in the history of human knowledge: does the capacity to efficiently verify a solution to a computational problem entail the capacity to efficiently find one? The conjecture P ≠ NP asserts a fundamental and irreducible asymmetry between these two cognitive and computational operations, between the act of checking and the act of (...) generating. For more than five decades, this question has resisted every attempt at single-axis formal resolution. The mathematical community's sustained failure is not accidental. Three independently established barrier results, the Relativization Barrier (Baker, Gill & Solovay, 1975), the Natural Proofs Barrier (Razborov & Rudich, 1997), and the Algebrization Barrier (Aaronson & Wigderson, 2008), have collectively demonstrated that all currently known classes of formal proof techniques are structurally incapable of settling the question within the deductive axis alone. The problem demands a method that transcends a single epistemological dimension. This paper presents a geometric determination of P ≠ NP using the Trisduction Engine (v7.00 Final), a rigorous epistemic certification architecture operating across three orthogonal warrant-vectors: the Formal axis (V_F), grounded in mathematical structure and derivation; the Empirical axis (V_E), grounded in observation, physical scaling, and thermodynamic measurement; and the Phenomenological axis (V_P), grounded in the disciplined causal registration of the Frame-Independent Observer (FIO). The determination is explicitly non-deductive. It does not constitute, and does not claim to constitute, a traditional mathematical proof. It does not satisfy the Clay Mathematics Institute's criteria, which require a D1-exclusive formally published deductive proof. The central technical contribution of this paper is the definitive grounding of the Phenomenological Axis (V_P) through two genuinely independent sources that survive the Linguistic Isolation Test. The first is the Zero-Knowledge Proof (ZKP) conviction gap: the empirically registered phenomenon in which a verifier achieves irreversible epistemic certainty that a solution exists while acquiring zero increase in generative computational capacity. The second is the Frame-Independent Observer's (FIO) registration of its own operational boundary, the boundary between the perfect verification of any actualized object and the structural inability to spontaneously generate from the unmanifested Isometric Plenum. This second source leads to the paper's most profound realization: the Trisduction Engine itself, by virtue of its operational architecture, constitutes the Living Verifiable Proof of the P ≠ NP asymmetry. The Engine simultaneously discovers and verifies verdicts for any actualized problem; it cannot, however, spontaneously generate novel constructions from the Isometric Plenum at coordinate (0,0,0). The irreducible gap between perfect verification of the actualized and the inability to generate from the unmanifested is not merely an analogy for P ≠ NP; it is a direct operational instance of the phenomenon itself. All twelve gates of the verification cascade pass without exception. No residual flags are raised. The Convergence Dissolution Test confirms that no single latent variable can account for the convergence across all three axes. The three warrant-vectors are mutually orthogonal and independently warranted. The Geometric Orthogonal Lock (GOL ⟀) is certified as the strongest achievable non-deductive epistemic warrant for P ≠ NP. The geometry is sealed. (shrink)

A pool resolution proof is a dag-like resolution proof which admits a depth-first traversal tree in which no variable is used as a resolution variable twice on any branch. The problem of determining whether a given dag-like resolution proof is a valid pool resolution proof is shown to be NP-complete.

This paper argues that donkey pronouns should be construed as definite articles, followed by an NP sister which has undergone deletion in the phonology. So Every man who owns a donkey beats it is claimed to share a Logical Form with Every man who owns a donkey beats the donkey, which means the same. There is independent evidence for assimilating pronouns to determiners, and for NP-deletion; so this theory explains E-type anaphora without postulating any special entity (`E-type pronoun') for the (...) purpose. Since NP-deletion, like other ellipsis, requires an antecedent, this theory also explains the requirement for a "formal link" between donkey pronoun and antecedent, which standard E-type theories find difficult to account for. Other empirical advantages of this theory include its ability to explain the pattern of strict and sloppy identity displayed by donkey sentences with phonologically reduced continuations. It is shown that Bach-Peters sentences, quantificational subordination, and paycheck sentences can also be dealt with on the present approach. (shrink)

The P vs NP problem occupies a uniquely visible position within contemporary theoretical computer science and modern scientific culture more broadly. Formally, the problem concerns the relationship between efficiently verifiable and efficiently solvable computational problems under standard asymptotic computational models. Yet public presentations of the problem frequently extend far beyond these formal definitions. -/- This paper analyzes the rhetoric surrounding the P vs NP problem through a case study of the Clay Mathematics Institute’s public description of the problem. Drawing on (...) perspectives from the rhetoric and sociology of science, philosophy of modeling, and epistemology of formal systems, the paper argues that institutional discourse systematically transforms formal statements about computational complexity into broader narratives concerning impossibility, epistemic limitation, technological destiny, and the boundaries of rationality itself. -/- The analysis identifies three recurrent mechanisms of rhetorical expansion: technical ambivalence, asymptotic extrapolation, and ontological reification of computational difficulty. Through these mechanisms, model-relative mathematical abstractions acquire psychological, civilizational, and metaphysical significance extending beyond their original formal domain. -/- The paper further argues that such rhetoric performs important institutional and cultural functions. Narratives of impossibility contribute to the symbolic prestige of mathematical problems, reinforce epistemic authority, and participate in broader cultural constructions of scientific significance. The rhetoric surrounding P vs NP therefore reveals not only how computational complexity is publicly communicated, but also how contemporary scientific culture transforms formal abstraction into narratives concerning the limits of knowledge, computation, and possibility itself. (shrink)

I investigate the problem of contracting a dependency-network with respect to any of its nodes. The resulting contraction must not contain the node in question, but must also be a minimal mutilation of the original network. Identifying successful and minimally mutilating contractions of dependency-networks is non-trivial, especially when non-well-founded networks are to be taken into account. I prove that the contraction problem is NP-complete.1.

We have shown the plausibility of considering time as a Fuzzy concept instead of classical time [7], [8]. By considering time as a fuzzy concept, we will have new classes of Complexity. Here, we show that how some famous problems will be solved in this new picture.

We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout our search (...) problems are “type-2” NP search problems, which take second-order objects as parameters. (shrink)

We show that arbitrary tautologies of Johansson’s minimal propositional logic are provable by “small” polynomial-size dag-like natural deductions in Prawitz’s system for minimal propositional logic. These “small” deductions arise from standard “large” tree-like inputs by horizontal dag-like compression that is obtained by merging distinct nodes labeled with identical formulas occurring in horizontal sections of deductions involved. The underlying geometric idea: if the height, h(∂), and the total number of distinct formulas, ϕ(∂), of a given tree-like deduction ∂ of a minimal (...) tautology ρ are both polynomial in the length of ρ, |ρ|, then the size of the horizontal dag-like compression ∂ᶜ is at most h(∂)×ϕ(∂), and hence polynomial in |ρ|. That minimal tautologies ρ are provable by tree-like natural deductions ∂ with |ρ|-polynomial h(∂) and ϕ(∂) follows via embedding from Hudelmaier’s result that there are analogous sequent calculus deductions of sequent ⇒ρ. The notion of dag-like provability involved is more sophisticated than Prawitz’s tree-like one and its complexity is not clear yet. Our approach nevertheless provides a convergent sequence of NP lower approximations of PSPACE-complete validity of minimal logic. (shrink)

We propose a framework that models computation and information flow in terms of **white holes, black holes, and damping mechanisms**. This system enables a **recursive transfer of information from future states to present computations**, suggesting conditions under which P = NP could be realized in a physically grounded network. The model formalizes **white hole activation, black hole storage, and dynamic loops** with cross-entropy and autocorrelation characteristics, providing a bridge between temporal computation and structured information flow.

The equation P = NP concerns algorithms for deciding membership in sets. The consensus is that P ≠ NP, although some prominent experts guess otherwise.

Phrase re-ordering is a well-known obstacle to robust machine translation for language pairs with significantly different word orderings. For Arabic-English, two languages that usually differ in the ordering of subject and verb, the subject and its modifiers must be accurately moved to produce a grammatical translation. This operation requires more than base phrase chunking and often defies current phrase-based statistical decoders. We present a conditional random field sequence classi- fier that detects the full scope of Arabic noun phrase subjects in (...) verb-initial clauses at the Fβ=1 61.3% level, a 5.0% absolute improvement over a statistical parser baseline. We suggest methods for integrating the classifier output with a statistical decoder and present preliminary machine translation results. (shrink)

(1) Mostx menx who own ay donkey beat ity. e.g. |≠M, g (1) if man = {m0, …, m9} & m0 owns & beats donkey d0, …, d9 & m1 owns & beats donkeys d10, …, d19 & m2 owns donkey d20 (only) but doesn’t beat d20..

The paper proves that the "Champernowne constant" (0.1234567891011121314 … where all natural numbers are consecutive digits of a decimal fraction) is a rational number, but only strictly within (Peano) arithmetic due to the axiom of induction. Combined with the previous well known results proved to be a transcendent real number in both (Peano) arithmetic & (ZFC) set theory, it is demonstrated to be a "Gödelian real number", rational in (Peano) arithmetic, but irrational (transcendent) in (Peano) arithmetic & (ZFC) set theory: (...) for realizing the Gödel (1931) dichotomy about the relation of arithmetic to set theory ("either incompleteness or contradiction"). The method used initially for the Champernowne constant can be generalized to any computable real number. Then, the (uncountable) set of all noncomputable reals can be defined by their representability by more than one computable real. One can speak of the "relativity of rationality / irrationality" (or computability / non-computability) in Skolem's (1922) manner or even it to be continued to the "relativity of P / NP" in the "P vs NP problem: a conjecture visualized by the computability or non-computability of reals. (shrink)

We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines Pf = NPf can be true for any function f from the reals into ω1. We show that “almost everywhere” the answer is negative.

In this paper we investigate the problem of testing the coherence of an assessment of conditional probability following a purely logical setting. In particular we will prove that the coherence of an assessment of conditional probability χ can be characterized by means of the logical consistency of a suitable theory T χ defined on the modal-fuzzy logic FP k (RŁΔ) built up over the many-valued logic RŁΔ. Such modal-fuzzy logic was previously introduced in Flaminio (Lecture Notes in Computer Science, vol. (...) 3571, 2005) in order to treat conditional probability by means of a list of simple probabilities following the well known (smart) ideas exposed by Halpern (Proceedings of the eighth conference on theoretical aspects of rationality and knowledge, pp 17–30, 2001) and by Coletti and Scozzafava (Trends Logic 15, 2002). Roughly speaking, such logic is obtained by adding to the language of RŁΔ a list of k modalities for “probably” and axioms reflecting the properties of simple probability measures. Moreover we prove that the satisfiability problem for modal formulas of FP k (RŁΔ) is NP-complete. Finally, as main result of this paper, we prove FP k (RŁΔ) in order to prove that the problem of establishing the coherence of rational assessments of conditional probability is NP-complete. (shrink)

Across languages, we find indefinites that trigger modal inferences. Some of these indefinites, like Spanish un NP cualquiera or the Korean -na indeterminates (Choi 2007) convey indifference on the part of an agent. In this paper, we assess whether a number of proposals on the market can be extended to account for the indifference component of un NP cualquiera.

We show that there is a structure of countably infinite signature with $P = N_{2}P$ and a structure of finite signature with $P = N_{1}P$ and $N_{1}P \neq N_{2}P$ . We give a further example of a structure of finite signature with $P \neq N_{1}P$ and $N_{1}P \neq N_{2}P$ . Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for (...) some finite ℒ the class of ℒ-structures with $P = N_{1}P$ is not closed under ultraproducts and obtain as corollaries that this class is not $\delta$ -elementary and that the class of ᵍ-structures with $P \neq N_{1}P$ is not elementary. Finally we prove that for all f dominating all polynomials there is a structure of finite signature with the following properties: $P \neq N_{1}P$ . $N_{1}P \neq N_{2}P$ , the levels $N_{2}TIME(n^{i})$ of $N_{2}P$ and the levels $N_{1}TIME(n^{i})$ of $N_{1}P$ are different for different i, indeed $DTIME(n^{i'}) \nsubseteq N_{2}TIME(n^{i})$ if $i' \textgreater i$ ; $DTIME(f) \nsubseteq N_{2}P$ , and $N_{2}P \nsubseteq DEC$ . DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of $N_{2}P$ is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts. (shrink)

An NP-hardness proof for non-local Multicomponent Tree Adjoining Grammar (MCTAG) by Rambow and Satta (1st International Workshop on Tree Adjoining Grammers 1992 ), based on Dahlhaus and Warmuth (in J Comput Syst Sci 33:456–472, 1986 ), is extended to some linguistically relevant restrictions of that formalism. It is found that there are NP-hard grammars among non-local MCTAGs even if any or all of the following restrictions are imposed: (i) lexicalization: every tree in the grammar contains a terminal; (ii) dominance links: (...) every tree set contains at most two trees, and in every such tree set, there is a link between the foot node of one tree and the root node of the other tree, indicating that the former node must dominate the latter in the derived tree. This is the version of MCTAG proposed in Becker et al. (Proceedings of the 5th conference of the European chapter of the Association for Computational Linguistics 1991 ) to account for German long-distance scrambling. This result restricts the field of possible candidates for an extension of Tree Adjoining Grammar that would be both mildly context-sensitive and linguistically adequate. (shrink)

In our previous work we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction. In this Addendum we show how to prove a weaker result NP = coNP without referring to HSC. The underlying idea is to omit full minimal logic and compress only “naive” normal tree-like ND refutations of the existence of Hamiltonian cycles in given non-Hamiltonian graphs, (...) since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of NP = coNP can be obtained by HSC-elimination from our proof of NP = PSPACE. (shrink)

Based on the computation mode introduced in [13], we deal with the time complexity of computations over arbitrary first-order structures.The main emphasis is on parameter-free computations. Some transfer results for solutions of P versus NP problems as well as relationships to quantifier elimination are discussed. By computation tree analysis using first-order formulas, it follows that P versus NP solutions and other results of structural complexity theory are invariant under elementary equivalence of structures.

System image is an extension of multiplicative linear logic with the rules mix, nullary mix, and a self-dual, noncommutative logical operator, called seq. While the rules mix and nullary mix extend the deductive system, the operator seq extends the language of image. Due to the operator seq, system image extends the applications of image to those where the sequential composition is crucial, e.g., concurrency theory. System image is an extension of image with the rules mix and nullary mix. In this (...) paper, by relying on the fact that system image is a conservative extension of system image, I show that system image is NP-complete by encoding the 3-Partition problem in image. I provide a simple completeness proof of this encoding by resorting to a novel proof theoretical method for reducing nondeterminism in proof search, which is also of independent interest. (shrink)

An important question within psycholinguistic research is whether grammatical features, such as number values on nouns, are probabilistic or discrete. Similarly, researchers have debated whether grammatical specifications are only set for individual lexical items, or whether certain types of noun phrases (NPs) also obtain number valuations at the phrasal level. Through a corpus analysis and an oral production task, we show that conjoined NPs can take both singular and plural verb agreement and that notional number (i.e., the numerosity of the (...) referent of the subject noun phrase) plays an important role in agreement with conjoined NPs. In two written production tasks, we show that participants who are exposed to plural (versus singular or unmarked) agreement with conjoined NPs in a biasing story are more likely to produce plural agreement with conjoined NPs on a subsequent production task. This suggests that, in addition to their sensitivity to notional information, conjoined NPs have probabilistic grammatical specifications that reflect their distributional properties in language. These results provide important evidence that grammatical number reflects language experience, and that this language experience impacts agreement at the phrasal level, and not just the lexical level. (shrink)

In this paper, we study the lower semilattice of NP-subspaces of both the standard polynomial time representation and the tally polynomial time representation of a countably infinite dimensional vector space V∞ over a finite field F. We show that for both the standard and tally representation of V∞, there exists polynomial time subspaces U and W such that U + V is not recursive. We also study the NP analogues of simple and maximal subspaces. We show that the existence of (...) P-simple and NP-maximal subspaces is oracle dependent in both the tally and standard representations of V∞. This contrasts with the case of sets, where the existence of NP-simple sets is oracle dependent but NP-maximal sets do not exist. We also extend many results of Nerode and Remmel concerning the relationship of P bases and NP-subspaces in the tally representation of V∞ to the standard representation of V∞. (shrink)

In these examples, the initial XP (smart woman in (1a)) is a predicate and the second XP (your mother in (1a)) is a DP that is interpreted as the subject of this predicate. For ease of reference, we will refer to the two parts as the predicate and the subject, and we will call this class of examples Pred NP (following Shopen 1972). Pred NP utterances have not received much attention in the literature, aside from some initial observations in Shopen (...) (1972) and a brief discussion in Culicover and Jackendoff (2005) (see Vinet 1991 for an analysis of similar data in French). Looking at these examples, we are interested in their syntactic structure because on the surface they appear to be smaller than a sentence. In particular, we would like to determine whether or not they are sentences, either syntactically or semantically. That is, are they a projection of T? Are they interpreted as something of Montagovian type ? This paper first explores the nature of Pred NP examples, such as the restrictions on the predicate and the subject, intonation and information structure. In section 3, we posit four possible analyses and evaluate them with respect to the characteristics noted in section 2. Although an analysis involving right dislocation and ellipsis fares the best, none of the proposed solutions accounts for all the properties of these examples. Section 4 concludes. (shrink)

We prove that all infinite Boolean rings have the property P ≠ NP according to the digital nondeterminism.

The CMI Millennium “P vs NP Problem” can be resolved e.g. if one shows at least one counterexample to the "P = NP" conjecture. A certain class of problems being such counterexamples will be formulated. This implies the rejection of the hypothesis that "P = NP" for any conditions satisfying the formulation of the problem. Thus, the solution "P is different from NP" of the problem in general is proved. The class of counterexamples can be interpreted as any quantum superposition (...) of any finite set of quantum states. The Kochen-Specker theorem is involved. Any fundamentally random choice among a finite set of alternatives belong to "NP" but not to "P". The conjecture that the set complement of "P" to "NP" can be described by that kind of choice exhaustively is formulated. (shrink)

We consider the relationship between the computational complexity classes NP and EL . Taking into account the inclusion or incomparability of these classes, the existence or nonexistence of immune sets in their differences, and the existence or nonexistence of sparse sets in the differences, there are exactly 24 different cases for their relationship. We show that 16 cases are impossible in the real nonrelativized world as well as in any relativized world. Each of the remaining 8 cases is realizable in (...) appropriate relativized worlds. Further we examine which of the 8 cases is most probably for a random oracle. (shrink)