你可能感興趣的試題

問(wèn)答題
【簡(jiǎn)答題】什么是算法A對(duì)于實(shí)例I的近似比、A的絕對(duì)近似比和漸進(jìn)近似比？
答案：算法A對(duì)于實(shí)例I的近似比（ratio factor）=RA（I）=max{A（I）/OPT（I），OPT（I）...
問(wèn)答題
【簡(jiǎn)答題】引入NP-完全性概念有什么意義？
答案：如果存在一臺(tái)DTM在多項(xiàng)式時(shí)間里接受某個(gè)NP-C語(yǔ)言，則所有NP類語(yǔ)言均可找到DTM在多項(xiàng)式時(shí)間里接受，從而有P=NP。...
問(wèn)答題
【簡(jiǎn)答題】什么是NP-完全性語(yǔ)言？什么是NP-完全性問(wèn)題？什么是NP-hard問(wèn)題？
答案：
問(wèn)答題
【簡(jiǎn)答題】Karp多項(xiàng)式規(guī)約是如何表述的？它與Cook多項(xiàng)式規(guī)約之間的關(guān)系如何？
答案：
問(wèn)答題
【簡(jiǎn)答題】什么是P類與NP類語(yǔ)言？如不用非確定性Turing機(jī)的概念，如何定義P類與NP類的問(wèn)題？
答案：語(yǔ)言族P=﹛L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)DTM接受的語(yǔ)言﹜
NP=﹛L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)N...
問(wèn)答題
【簡(jiǎn)答題】非確定性Turing機(jī)的時(shí)間復(fù)雜度是如何定義的？
答案：NDTM的時(shí)間復(fù)雜度T（n）：對(duì)于可接受的輸入串，T（n）=max{關(guān)于輸入|ω的時(shí)間復(fù)雜度ω的...
問(wèn)答題
【簡(jiǎn)答題】非確定性Turing機(jī)與確定性Turing機(jī)的主要區(qū)別在什么地方？
答案：與DTM不同的是，NDTM的每一步動(dòng)作允許有若干個(gè)選擇，對(duì)于給定的Q×Tk的一個(gè)元素（qi， a1，a2，&#...
問(wèn)答題
【簡(jiǎn)答題】Turing機(jī)所接受的語(yǔ)言是什么樣的語(yǔ)言？各種語(yǔ)言之間有什么樣的關(guān)系？
答案：Turing可計(jì)算函數(shù)部分遞歸函數(shù)。
遞歸可枚舉集>（完全）遞歸集>原始遞歸集
部分遞歸函數(shù)>完全遞...
問(wèn)答題
【簡(jiǎn)答題】RAM程序、RASP程序與Turing機(jī)相互之間的時(shí)間復(fù)雜度關(guān)系是怎樣的（考慮兩種耗費(fèi)標(biāo)準(zhǔn)）？
答案：任何一個(gè)RAM程序，都可由一個(gè)RASP程序來(lái)模擬實(shí)現(xiàn)，且時(shí)間復(fù)雜性數(shù)量級(jí)相同（不論哪一種耗費(fèi)標(biāo)準(zhǔn)）。即如果RAM程序的時(shí)...
問(wèn)答題
【簡(jiǎn)答題】Church-Turing Thesis的內(nèi)容是什么？它有什么意義？
答案：任何合理的計(jì)算模型都是相互等價(jià)的（計(jì)算范圍相同）。
合理：?jiǎn)挝粫r(shí)間內(nèi)可以完成的工作量，有一個(gè)多項(xiàng)式的上限。不合...

首頁(yè)

題庫(kù)

網(wǎng)課

在線?？?/h3>

桌面端

【簡(jiǎn)答題】什么是多項(xiàng)式時(shí)間近似方案（PTAS）？什么是完全多項(xiàng)式時(shí)間近似方案（FPTAS，F(xiàn)PAS）？

你可能感興趣的試題

【簡(jiǎn)答題】什么是算法A對(duì)于實(shí)例I的近似比、A的絕對(duì)近似比和漸進(jìn)近似比？

【簡(jiǎn)答題】引入NP-完全性概念有什么意義？

【簡(jiǎn)答題】什么是NP-完全性語(yǔ)言？什么是NP-完全性問(wèn)題？什么是NP-hard問(wèn)題？

【簡(jiǎn)答題】Karp多項(xiàng)式規(guī)約是如何表述的？它與Cook多項(xiàng)式規(guī)約之間的關(guān)系如何？

【簡(jiǎn)答題】什么是P類與NP類語(yǔ)言？如不用非確定性Turing機(jī)的概念，如何定義P類與NP類的問(wèn)題？

【簡(jiǎn)答題】非確定性Turing機(jī)的時(shí)間復(fù)雜度是如何定義的？

【簡(jiǎn)答題】非確定性Turing機(jī)與確定性Turing機(jī)的主要區(qū)別在什么地方？

【簡(jiǎn)答題】Turing機(jī)所接受的語(yǔ)言是什么樣的語(yǔ)言？各種語(yǔ)言之間有什么樣的關(guān)系？

【簡(jiǎn)答題】RAM程序、RASP程序與Turing機(jī)相互之間的時(shí)間復(fù)雜度關(guān)系是怎樣的（考慮兩種耗費(fèi)標(biāo)準(zhǔn)）？

【簡(jiǎn)答題】Church-Turing Thesis的內(nèi)容是什么？它有什么意義？

【簡(jiǎn)答題】什么是多項(xiàng)式時(shí)間近似方案（PTAS）？什么是完全多項(xiàng)式時(shí)間近似方案（FPTAS，F(xiàn)PAS）？

你可能感興趣的試題

【簡(jiǎn)答題】什么是算法A對(duì)于實(shí)例I的近似比、A的絕對(duì)近似比和漸進(jìn)近似比？

【簡(jiǎn)答題】引入NP-完全性概念有什么意義？

【簡(jiǎn)答題】什么是NP-完全性語(yǔ)言？什么是NP-完全性問(wèn)題？什么是NP-hard問(wèn)題？

【簡(jiǎn)答題】Karp多項(xiàng)式規(guī)約是如何表述的？它與Cook多項(xiàng)式規(guī)約之間的關(guān)系如何？

【簡(jiǎn)答題】什么是P類與NP類語(yǔ)言？如不用非確定性Turing機(jī)的概念，如何定義P類與NP類的問(wèn)題？

【簡(jiǎn)答題】非確定性Turing機(jī)的時(shí)間復(fù)雜度是如何定義的？

【簡(jiǎn)答題】非確定性Turing機(jī)與確定性Turing機(jī)的主要區(qū)別在什么地方？

【簡(jiǎn)答題】Turing機(jī)所接受的語(yǔ)言是什么樣的語(yǔ)言？各種語(yǔ)言之間有什么樣的關(guān)系？

【簡(jiǎn)答題】RAM程序、RASP程序與Turing機(jī)相互之間的時(shí)間復(fù)雜度關(guān)系是怎樣的（考慮兩種耗費(fèi)標(biāo)準(zhǔn)）？

【簡(jiǎn)答題】Church-Turing Thesis的內(nèi)容是什么？它有什么意義？

【簡(jiǎn)答題】什么是多項(xiàng)式時(shí)間近似方案（PTAS）？什么是完全多項(xiàng)式時(shí)間近似方案（FPTAS，F(xiàn)PAS）？

【簡(jiǎn)答題】什么是算法A對(duì)于實(shí)例I的近似比、A的絕對(duì)近似比和漸進(jìn)近似比？

【簡(jiǎn)答題】什么是NP-完全性語(yǔ)言？什么是NP-完全性問(wèn)題？什么是NP-hard問(wèn)題？

【簡(jiǎn)答題】Karp多項(xiàng)式規(guī)約是如何表述的？它與Cook多項(xiàng)式規(guī)約之間的關(guān)系如何？

【簡(jiǎn)答題】什么是P類與NP類語(yǔ)言？如不用非確定性Turing機(jī)的概念，如何定義P類與NP類的問(wèn)題？

【簡(jiǎn)答題】非確定性Turing機(jī)的時(shí)間復(fù)雜度是如何定義的？

【簡(jiǎn)答題】非確定性Turing機(jī)與確定性Turing機(jī)的主要區(qū)別在什么地方？

【簡(jiǎn)答題】Turing機(jī)所接受的語(yǔ)言是什么樣的語(yǔ)言？各種語(yǔ)言之間有什么樣的關(guān)系？

【簡(jiǎn)答題】RAM程序、RASP程序與Turing機(jī)相互之間的時(shí)間復(fù)雜度關(guān)系是怎樣的（考慮兩種耗費(fèi)標(biāo)準(zhǔn)）？

【簡(jiǎn)答題】Church-Turing Thesis的內(nèi)容是什么？它有什么意義？