2. 您的位置
3. 首页
4. 期刊论文
5. SOME UNPROVABLE TRUE PROPOSITIONS IN COMPLEXITY

SOME UNPROVABLE TRUE PROPOSITIONS IN COMPLEXITY

来源 :科学通报：英文版 | 被引量 : 0次 | 上传用户：baihuiguo

【摘 要】

：

<正> 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 f

【作 者】

：

洪加威 

【机 构】

：

BeijingComPuterInstitute

【出 处】

：

科学通报：英文版

【发表日期】

：

1983年10期

【关键词】

：

BOUNDS TRIVIAL EXPONENTIAL TRUE think repeatedly 幼君 progr 

下载到本地 , 更方便阅读

下载此文 赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

<正> 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

其他文献

反倾销应诉，彩电厂家各怀心思

期刊

彩电企业反倾销市场销售彩电厂家

INFINITESIMAL BACKLUND TRANSFORMATIONS OF SINEGORDON EQUATION

<正> Theorem 2. The infinitesimal Backlund transformnations Bλ+εBγ-1 of the sine-Gordon equation are permutable if and only if the conserred densities of the

期刊

班位艺初三刀

STUDIES ON BIS(ALKYLCYCLOPENTADIENYL)-DI-(ARYLOXY) METALDERIVATIVES

<正> We have studied systematically the reactions of bis(cyclopentadienyl)metal dichlorides with phenol or substituted phenols and ’HNMR of aryloxy derivatives

期刊

PHENOLSSUBSTITUTEDsystematicallyderivquids史公

ON THE ALMOST EVERYWHERE CONVERGENCE OF A KIND OF INTEGRALS

<正> In the approximation theory and harmonic analysis, we often need to investigate the integrals dt. We have already proved the following theorem: If the func

期刊

HARMONIC王玄君才了公

AN APPLICATION OF LYAPUNOV DIRECT METHOD TO THE STABILITY PROBLEM OF SPINNING SOLID BODIES WITH LIQU

<正> The motion stability problem of continuous systems is usually treated by two methods; the normal mode approach and the global approach, including the Lyapu

期刊

latterSOLIDFREEDOMsatisfyeliminatingtransformedconvergeINERTIAFILLEDadd

REGRESSION SIMULATION OF ENZYME-CATALYZINGKINETICS——A DEVELOPMENT FROM THE HILL EQUATION

<正> Many enzymes that play an important part in biological reactive system yield kinetic curves based on the Hill equation for the oxygen-hemoglobin system, an

期刊

HEMOGLOBINENZYMESSATURATION五甲二万

A NOTE ON PERKO’S 'ON LIMIT CYCLES OF QUADRATIC SYSTEM IN E~2'

<正> In his paper On rotated veotor fields and the global behavior of limit cycles of a class of quadratic system in the plane (J. Diff. Eqs., 18(1975), 63—86)

期刊

QUADRATIC油竹atmos

SYSTEM ANATOMY AND ORGANOHISTOLOGY OF GIANT PANDA (AILUROPODA MELANOLEUCA)

<正> A systemic morphological research of Giant panda including its system anatomy and organohistology was carried out from December 1980 to June 1983. Seven ad

期刊

PANDAEVOLUTIONARYGiantNEWBORNANATOMYecologyimpliesyoungBROWNmorphologic

MECHANISM OF THE REPLICATION OF CYTOPLASMIC POLYHEDROSIS VIRUS OF THE SILKWORM, BOMBYX MORI

<正> The cytoplasmic polyhedrosis virus (CPV) of silkworm was conveniently purified in large quantities under mild coditions by means of gel column chromatograp

期刊

convenientlyQUANTITIEStranscribedCYTOPLASMICinsteadpurifiedSILKWORMRNAPO

DIFFERENTIAL METHODS OF OPTIMIZATION

<正> In this letter we shall deal with problems of optimization by using ordinary differential equations. The limit point of the path of the initial value probl

期刊

ordinaryLETTEREQUALITYARBITRARY少双以通