Suppose that we want to compute any number by means of operations like +, -, *, /, and suppose that in one step we can get the exact value of the operation performed. Then the number t(n) of the steps needed to obtain...Suppose that we want to compute any number by means of operations like +, -, *, /, and suppose that in one step we can get the exact value of the operation performed. Then the number t(n) of the steps needed to obtain n approximate digits of the final result is either O(1) or Ω(log n). There is a gap.展开更多
In this letter, we prove that in order to determine whether a proposition in elementary geometry of a certain type is true, we need only to compute one concrete example which depends only on the length of the proposit...In this letter, we prove that in order to determine whether a proposition in elementary geometry of a certain type is true, we need only to compute one concrete example which depends only on the length of the proposition and the number n of free variables involved.展开更多
In complexity theory, upper bounds have been improved repeatedly, but little has been obtained in the field of lower bounds.For example, the upper bounds for any NP-complete problem are exponential, but there is only ...In complexity theory, upper bounds have been improved repeatedly, but little has been obtained in the field of lower bounds.For example, the upper bounds for any NP-complete problem are exponential, but there is only a trivial linear lower bound. Thisfaet makes us think that some true propositions in complexity are unprovable. But if we get a result like the G?del’s in-展开更多
Whether or not the group isomorphism problem is tractable is still an important open problem. But for Abelian groups of order n, C. Savage has an algorithm of time complexity O(n^2) to determine whether they are isomo...Whether or not the group isomorphism problem is tractable is still an important open problem. But for Abelian groups of order n, C. Savage has an algorithm of time complexity O(n^2) to determine whether they are isomorphic, given their multiplication table as input. Notice that the length of the input is of order n^2, therefore this is a linear time algorithm.展开更多
Ⅰ. INTRODUCTIONWe have many models of computation, many computational types and many different resources. There are, therefore, thousands of theorems on relations between the above items. Unfortunately, we do not yet...Ⅰ. INTRODUCTIONWe have many models of computation, many computational types and many different resources. There are, therefore, thousands of theorems on relations between the above items. Unfortunately, we do not yet have a clear picture of those relationships. The most important problem right now, therefore, is not to prove some individual theorems but to unify the whole theory. With this in mind, the author proposed the similarity and duality of computation, proved three similarity theorems and a series meta-theorems in dual form, thereby unifying all the computational models, types and theorems in a certain field, and got some results which are completely new. Readers can see [1, 4, 5, 7, 9] for historical reference.展开更多
文摘Suppose that we want to compute any number by means of operations like +, -, *, /, and suppose that in one step we can get the exact value of the operation performed. Then the number t(n) of the steps needed to obtain n approximate digits of the final result is either O(1) or Ω(log n). There is a gap.
文摘In this letter, we prove that in order to determine whether a proposition in elementary geometry of a certain type is true, we need only to compute one concrete example which depends only on the length of the proposition and the number n of free variables involved.
文摘In complexity theory, upper bounds have been improved repeatedly, but little has been obtained in the field of lower bounds.For example, the upper bounds for any NP-complete problem are exponential, but there is only a trivial linear lower bound. Thisfaet makes us think that some true propositions in complexity are unprovable. But if we get a result like the G?del’s in-
文摘Whether or not the group isomorphism problem is tractable is still an important open problem. But for Abelian groups of order n, C. Savage has an algorithm of time complexity O(n^2) to determine whether they are isomorphic, given their multiplication table as input. Notice that the length of the input is of order n^2, therefore this is a linear time algorithm.
文摘Ⅰ. INTRODUCTIONWe have many models of computation, many computational types and many different resources. There are, therefore, thousands of theorems on relations between the above items. Unfortunately, we do not yet have a clear picture of those relationships. The most important problem right now, therefore, is not to prove some individual theorems but to unify the whole theory. With this in mind, the author proposed the similarity and duality of computation, proved three similarity theorems and a series meta-theorems in dual form, thereby unifying all the computational models, types and theorems in a certain field, and got some results which are completely new. Readers can see [1, 4, 5, 7, 9] for historical reference.
