Now showing items 21-40 of 56

    • On Complete Problems for NP$\cap$CoNP 

      Hartmanis, Juris; Immerman, Neil (Cornell University, 1985-04)
      It is not known whether complete languages exist for $NP\cap CoNP$, and Sipser has shown that there are relativizations so that $NP\cap CoNP$ has no $\leq ^{P}_{m}$-complete languages. In this paper we show that $NP\cap ...
    • On Effective Speed-up and Long Proofs of Trivial Theorems in Formal Theories 

      Hartmanis, Juris (Cornell University, 1975-07)
      In this note we give a very simple proof which shows that in many interesting formal mathematical theories, axiomatizable as well as decidable ones, for every given formalization we can effectively find infinite subsets ...
    • On Goedel Speed-Up and Succinctness of Language Representation 

      Hartmanis, Juris (Cornell University, 1982-03)
      In this note we discuss the similarities and differences between Goedel's result about non-recursive shortening of proofs of formal systems by additional axioms and the corresponding results about the succinctness of ...
    • On IP=PSPACE and Theorems with Narrow Proofs 

      Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj (Cornell University, 1990-05)
      Very recently, it was shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible computations. ...
    • On Isomorphisms and Density of NP and Other Complete Sets 

      Hartmanis, Juris; Berman, L. (Cornell University, 1975-10)
      If all NP complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then P $\neq$ NP and if all PTAPE complete sets are p-isomorphic then P $\neq$ PTAPE. We show that all NP complete sets ...
    • On Log-Tape Isomorphisms of Complete Sets 

      Hartmanis, Juris (Cornell University, 1977-07)
      In this paper we study $\log n$-tape computable reductions between sets and investigate conditions under which $\log n$-tape reductions between sets can be extended to $\log n$-tape computable isomorphisms of these sets. ...
    • On Non-Isomorphic NP Complete Sets 

      Hartmanis, Juris (Cornell University, 1983-10)
      In this note we show that if the satisfiability of Boolean formulas of low Kolmogorov complexity can be determined in polynomial-time then there exist NP complete sets that are not polynomial-time isomorphic. Keywords: ...
    • On Polynomial Time Isomorphism of Complete Sets 

      Berman, L.; Hartmanis, Juris (Cornell University, 1976-12)
      IN this note we show that the recently discovered NP complete sets arising in number theory, the PTAPE complete sets arising in game theory and EXPTAPE complete sets arising from algebraic word problems are polynomial ...
    • On Simple Goedel Numberings and Translations 

      Hartmanis, Juris; Baker, Theodore Paul (Cornell University, 1973-07)
      In this paper we consider Goedel numberings (viewed as simple models for programming languages) into which all other Goedel numberings can be translated very easily. Several such classes of Goedel numberings are defined ...
    • On Sparse Oracles Separating Feasible Complexity Classes 

      Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 1985-10)
      This note clarifies which oracles separate NP from P and which do not. In essence, we are changing our research paradigm from the study of which problems can be relativized in two conflicting ways to the study and ...
    • On Sparse Sets in NP-P 

      Hartmanis, Juris (Cornell University, 1982-08)
      The main result of this note shows that there exist sparse sets in $NP$ that are not in $P$ if and only if NEXPTIME differs from EXPTIME. Several other results are derived about the complexity of very sparse sets in ...
    • On the Importance of Being II2-Hard 

      Hartmanis, Juris (Cornell University, 1989-01)
      In this column, we show how a variety of interesting results in theory of computation all follow from a simple observation about $\prod _{2}$-complete sets of total machines. We easily derive: a) representation independent ...
    • On the Intellectual Terrain Around NP 

      Hartmanis, Juris; Chari, Suresh (Cornell University, 1993-12)
      In this paper, we view $P \stackrel{?}{=} NP$ as the problem which symbolizes the attempt to understand what is and what is not feasibly computable. The paper shortly reviews the history of the developments from Godel's ...
    • On the Power of Multiplication in Random Access Machines 

      Hartmanis, Juris; Simon, Janos (Cornell University, 1974-09)
      We consider random access machines with a multiplication operation, having the added capability of computing logical operations on bit vectors in parallel. The contents of a register are considered both as an integer and ...
    • On the Problem of Finding Natural Computational Complexity Measures 

      Hartmanis, Juris (Cornell University, 1973-06)
      To develop an abstract theory which deals with the quantitative aspects of computing we need a deeper understanding of how to define "natural" computational complexity measures axiomatically. To this end, this paper ...
    • On the Recognition of Primes by Automata 

      Hartmanis, Juris; Shank, H. (Cornell University, 1968-02)
      A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of primes can be accepted by a ...
    • On the Structure of Feasible Computations 

      Hartmanis, Juris; Simon, Janos (Cornell University, 1974-08)
      During the last four years research on the lower level computational complexity has yielded a rich set of interesting results which have revealed deep and unexpected connections between various problems and thus brought ...
    • On the Structure of Feasible Computations 

      Hartmanis, Juris (Cornell University, 1982-03)
      This paper discusses the study of computational complexity of feasible computations and surveys some recent insights and results about the structure of NP complete languages and the attempts to separate the classic ...
    • On the Succintness of Different Representations of Languages 

      Hartmanis, Juris (Cornell University, 1978-06)
      The purpose of this paper is to give simple new proofs of some interesting recent results about the relative succintness of different representations of regular, deterministic and unambiguous context-free languages and ...
    • One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets 

      Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 1986-01)
      This paper 1. gives a relativized counterexample to the conjectured connection between the existence of one-way functions and the existence of non-isomorphic NP-complete sets. 2. establishes that in relativized worlds ...