The presence of dual and ambivalent characters (good/ bad) has always constituted the aesthetic and educational content in children’s fairy tales. Since the Nineteenth century, fairy tales and children’s books have had as an essential reference increasingly complex images and illustrations with vivid colors. This, together with the narration, has allowed the flourishing of a genre of fairy tale noir, whose explicitly pedagogical content is grafted into the plots not always “to happy ending” of fairy tales. The book by Heinrich (...) Hoffmann, _Struwwelpeter_, and that by Ernst Theodor Hoffmann, _Der Sandmann_, which are at the heart of this essay, constituted a first, important example of this new kind of narrative. They have revealed, from a pedagogical-psychoanalytic perspective, the value of what Freud in a 1919 paper, _Das Unheimliche_, analyzed as a necessary manifestation of presence/absence (conscious and unconscious) in the phases of human growth. (shrink)

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)

Edward Said was a versatile intellectual, anchored in a solid humanistic culture, who, in his career as a public figure as a university Professor at Columbia, placed at the center of his reflections the sense of commitment of the man of culture. His multifaceted education and his interests are the summit of an attention to the generative issues of pedagogical and educational culture, aimed at redefining a new “radical humanism.” For Said, however, the commitment and careful examination of texts and (...) reality can only pass through an effort of critical thinking, capable of acquiring its own autonomy of judgment and, for this reason, point out and highlight the differences of all forms of power and coercion. (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)

D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too.

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

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

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 prove that all infinite Boolean rings (algebras) have the property P ≠ NP according to the digital (binary) nondeterminism.

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).

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)

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.

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)

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)

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.

(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..

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.

I articulate a novel modal argument for P=NP.

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)

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.

We upgrade [3] to a complete proof of the conjecture NP = PSPACE that is known as one of the fundamental open problems in the mathematical theory of computational complexity; this proof is based on [2]. Since minimal propositional logic is known to be PSPACE complete, while PSPACE to include NP, it suffices to show that every valid purely implicational formula ρ has a proof whose weight and time complexity of the provability involved are both polynomial in the weight of (...) ρ. As is [3], we use proof theoretic approach. Recall that in [3] we considered any valid ρ in question that had a “short” tree-like proof π in the Hudelmaier-style cutfree sequent calculus for minimal logic. The “shortness” means that the height of π and the total weight of different formulas occurring in it are both polynomial in the weight of ρ. However, the size, and hence also the weight, of π could be exponential in that of ρ. To overcome this trouble we embedded π into Prawitz’s proof system of natural deductions containing single formulas, instead of sequents. As in π, the height and the total weight of different formulas of the resulting tree-like natural deduction ∂1 were polynomial, although the size of ∂1 still could be exponential, in the weight of ρ. In our next, crucial move, ∂1 was deterministically compressed into a “small”, although multipremise, dag-like deduction ∂ whose horizontal levels contained only mutually different formulas, which made the whole weight polynomial in that of ρ. However, ∂ required a more complicated verification of the underlying provability of ρ. In this paper we present a nondeterministic compression of ∂ into a desired standard dag-like deduction ∂0 that deterministically proves ρ in time and space polynomial in the weight of ρ.2 Together with [3] this completes the proof of NP = PSPACE.Natural deductions are essential for our proof. Tree-to-dag horizontal compression of π merging equal sequents, instead of formulas, is not sufficient, since the total number of different sequents in π might be exponential in the weight of ρ – even assuming that all formulas occurring in sequents are subformulas of ρ. On the other hand, we need Hudelmaier’s cutfree sequent calculus in order to control both the height and total weight of different formulas of the initial tree-like proof π, since standard Prawitz’s normalization although providing natural deductions with the subformula property does not preserve polynomial heights. It is not clear yet if we can omit references to π even in the proof of the weaker result NP = coNP. (shrink)

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)

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)

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.

コンピュータの歴史、アルゴリズムの理論の解説を経て、未解決であるミレニアム問題のひとつ、「P≠NP問題」に迫ります!

Selmer Bringsjord & Joshua Taylor∗ Department of Cognitive Science Department of Computer Science The Rensselaer AI & Reasoning (RAIR) Lab Rensselaer Polytechnic Institute (RPI) Troy NY 12180 USA http://www.rpi.edu/∼brings {selmer,tayloj}@rpi.edu..

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

The construction we are discussing is a recent American English construction with an individual-denoting noun phrase in the predicate position modified by a degree modifier that typically occurs with gradable adjectives, as in 'This is so Obama!' We attempt to look deeper into the structure and compositional semantics of this construction, and though we do not provide a complete analysis of it, we believe that the study of this construction can contribute to questions of gradable predicate semantics, multidimensionality, degree constructions (...) and proper name semantics. (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.

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)

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)

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)

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.