We study the computability of the Lebesgue measure of a two-dimensional region that has a polynomial-time computable boundary. It is shown that the two-dimensional measure of the boundary itself completely characterizes the computability of the measure of the interior region. Namely, if a polynomial-time computable, simple, closed curve has measure zero, then its interior region must have a computable measure. Conversely, if such a curve has a positive measure, then the measure of its interior region could be any positive, left r.e. real number.

The computational complexity of bounded sets of the two-dimensional plane is studied in the discrete computational model. We introduce four notions of polynomial-time computable sets in ${\bf R}^{2}$ and study their relationship. The computational complexity of the winding number problem, membership problem, distance problem, and area problem is characterized by the relations between discrete complexity classes of the NP theory.

We introduce a measure for the computational complexity of mdiwdual instances of a decision problem and study some of Its properties.The instance complexity of a string ~with respect to a set A and time bound t, ict(x : A). is defined as the size of the smallest special-case program for A that run> m time t,decides x correctly, and makes no mistakes on other strings ("don't know" answers are permitted).We prove that a set A is m P if and only if there exist a polynomial t and a constant c such that ic'(x : A) < c for all X; on the other hand, If A ]s NP-hard and P # NP, then for all polynomials t and constants c. lc'(~: A) > c log I ~I for ]nfimtely many x.Obserwng that Kf(x), the t-bounded Kolmogorov complexity of x, N roughly an upper bound on ]Ct(.t: A), we proceed to investigate the existence of mdiwdually hard problem Instances.].e , strings whose instance complexity E close to their Kolmogorov complexity.We prove that if t(n) z n is a time-constructible function and A 1s a recurswe set not in DTIME(t), there then exist a constant c and mfimtely many I such that ic'(x : ,4) z K' (x) -c. for some Prehmmary versions of parts of this work have appeared under the titles "What 1s a hard instance of a computational problem?" m Proceedings of tize Conference on Structare m Cornplexm Theory (Berkeley, Calif., June i 986), and "On the instance complexity of NP-hard problems" in Procecduzgs of the 5tk .4nrrualConference on StntctLwe m Cowrpkwty Theory (Barcelona, Spain, July 1990).

Article Some complexity issues on the simply connected regions of the two-dimensional plane Share on Authors: Arthur W. Chou View Profile , Ker-I Ko View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 1–10https://doi.org/10.1145/167088.167093Online:01 June 1993Publication History 2citation145DownloadsMetricsTotal Citations2Total Downloads145Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Integral equations, systems of quadratic equations, and exponential time completeness Author: Ker-I. Ko Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NYView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 10–20https://doi.org/10.1145/103418.103427Online:03 January 1991Publication History 1citation374DownloadsMetricsTotal Citations1Total Downloads374Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The following problems about time-bounded program-size complexity are studied: (1) for a given string x, a size bound s, and a time bound t, whether there exists a Turing machine of size less than or equal to s that prints x in t moves; (2) for two given finite sets Y and Z of strings, a size bound s, and a time bound t, whether there exists a Turing machine of size less than or equal to s that operates in time t and accepts all $y \in Y$ and rejects all $z \in Z$. These problems are fundamental in complexity theory and feasible learning theory. The complexity of these problems is apparently between P and $NP$, but appears very difficult to classify precisely. These problems are attacked by the approach of relativization. It is shown that for certain variations of the problems, they could be either polynomial-time computable or not polynomial-time computable, depending on different oracles. Furthermore, there are oracles relative to which they are not complete for $NP$ under the polynomial-time Turing reductions, but are complete for $NP$ under the strong $NP$ reductions.

The probabilistic polynomial-time hierarchy (BPH) is the hierarchy generated by applying the BP-operator to the Meyer-Stockmeyer polynomial-time hierarchy (PH), where the BP-operator is the natural generalization of the probabilistic complexity class BPP. The similarity and difference between the two hierarchies BPH and PH is investigated. Oracles A and B are constructed such that both PH( A ) and PH( B ) are infinite while BPH( A ) is not equal to PH( A ) at any level and BPH( B ) is identical to PH( B ) at every level. Similar separating and collapsing results in the case that PH( A ) is finite having exactly k levels are also considered.

An attempt is made to give a more accurate classification of the computational complexity of roots of real functions. Attention is focused on the simplest types of functions, namely, one-to-one and k-to-one functions, and the complexity of their roots is characterized in terms of relations between discrete complexity classes, such as LOGSPACE, P, UP, and NP.>

It is proved that for every integer $k \geqq 0$, there is an oracle $A_k $ relative to which the polynomial time hierarchy collapses so that it has exactly k levels. Furthermore, sets $B_k $ and $C_k $ may be constructed so that, relative to $B_k $, the polynomial time hierarchy has exactly k levels and the class PSPACE coincides with the polynomial time hierarchy, and, relative to $C_k $, the polynomial time hierarchy has exactly k levels and the class PSPACE is different from the polynomial time hierarchy.

Article Free Access Share on Relativized polynomial time hierarchies having exactly K levels Author: Ker-I Ko Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NYView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 245–253https://doi.org/10.1145/62212.62235Online:01 January 1988Publication History 4citation270DownloadsMetricsTotal Citations4Total Downloads270Last 12 Months11Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We study sets that are truth-table reducible to sparse sets in polynomial time. The principal results are as follows: (1) For every integer $k > 0$, there is a set L and a sparse set S such that $L \leqq _{(k + 1) - tt}^P S$, but there is no sparse set $S'$ such that $L \leqq _{k - tt}^P S'$. (2) There exist a sparse set S and a set L such that $L \leqq _{tt}^P S$ but there is no integer k such that for some sparse $S'$, $L \leqq _{k - tt}^P S'$. (3) The class of sets that are bounded truth-table reducible to tally sets is equal to the class of sets that are many–one reducible to tally sets. (4) The class of sets having polynomial-size circuits is equal to the class of sets that are truth-table reducible to tally sets. Similar results are developed for truth-table reducibilities that are computed nondeterministically in polynomial time or in polynomial space.

A group testing problem with two irregular coins and with a test device that detects only an underweight coin is considered. The maximum number of tests required to identify two irregulars, one overweight and one underweight, is known to have a lower bound of $2\log n$. We present a procedure that gives an upper bound of $2\log n + O ( \log \log n\sqrt {\log n} )$.

Article Free Access Share on A note on one-way functions and polynomial-time isomorphisms Authors: K I Ko Department of Computer Science, University of Houston, Houston, Tx and Mathematical Sciences Research Institute, Berkeley, Ca. Department of Computer Science, University of Houston, Houston, Tx and Mathematical Sciences Research Institute, Berkeley, Ca.View Profile , T J Long Department of Computer and Information Science, The Ohio State University, Columbus, Oh. Department of Computer and Information Science, The Ohio State University, Columbus, Oh.View Profile , D Z Du Mathematical Sciences Research Institute, Berkeley, Ca. Mathematical Sciences Research Institute, Berkeley, Ca.View Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 295–303https://doi.org/10.1145/12130.12160Published:01 November 1986Publication History 4citation223DownloadsMetricsTotal Citations4Total Downloads223Last 12 Months12Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let A be a set having polynomial size circuits. If A is also known to be in NP, then we may conclude that the graph of the polynomial size circuits for A is actually in $\Pi _2^p $. Using this observation, we show that sets in NP which have polynomial size ciruits are in $L_3^p $, the third level of the low hierarchy in NP. By a similar technique, we are able to show that some other intuitively low sets in NP are in $L_2^p $, and even in a certain refinement of $L_2^p $. As a consequence, sparse sets are not strong nondeterministic polynomial time Turing complete in NP unless the polynomial time hierarchy collapses to $\Delta _2^p $.

Polynomial time approximations to exponential time computable problems (EXP) are considered from the point of view of structure. Infinitely often speedable and almost everywhere complex problems are studied using the notions of polynomial time productivity and immunity. In particular, the existence of a polynomial time immune set which is not polynomial time approximable at all but which is polynomial time $tt$-complete in EXP is proven. The relationship between completeness and approximability is also studied. It is shown that being polynomial time m-complete in EXP does not provide any control of the probability of erroneous approximations.