Untuk setiap fungsi yang dapat dihitung,

19

Untuk setiap fungsi yang dapat dihitung apakah ada masalah yang dapat diselesaikan paling baik dalam waktu atau adakah fungsi yang dapat dihitung sehingga setiap masalah yang dapat diselesaikan dalam dapat juga dipecahkan dalam waktu ? $f$ $\Theta(f(n))$ $f$ $O(f(n))$ $o(f(n))$

Pertanyaan ini muncul di kepala saya kemarin. Saya sudah memikirkannya sedikit sekarang, tetapi tidak bisa mengetahuinya. Saya tidak benar-benar tahu bagaimana saya google untuk ini, jadi saya bertanya di sini. Inilah yang saya buat:

Pikiran pertama saya adalah bahwa jawabannya adalah ya: Untuk setiap fungsi dihitung masalah "Output titik" (atau membuat string dengan titik atau apa pun) dapat jelas tidak diselesaikan dalam waktu. Jadi kita hanya perlu menunjukkan bahwa itu dapat diselesaikan dalam waktu . Tidak masalah, ambil saja kode pseudo berikut: $f$ $f(n)$ $f(n)$ $o(f(n))$ $O(f(n))$

x = f(n)
for i from 1 to x:
    output(".")

Jelas bahwa algoritma memecahkan masalah yang dinyatakan. Dan itu runtime jelas di , jadi masalah terpecahkan. Itu mudah, bukan? Kecuali tidak, itu bukan karena Anda harus mempertimbangkan biaya baris pertama. Algoritma runtime di atas hanya dalam jika waktu yang dibutuhkan untuk menghitung adalah dalam . Jelas itu tidak benar untuk semua fungsi ¹ . $\Theta(f(n))$ $\Theta(f(n))$ $f(n)$ $O(f(n))$

Jadi pendekatan ini tidak membuat saya ke mana pun. Saya akan berterima kasih kepada siapa pun yang menunjukkan saya ke arah yang benar untuk mengetahui hal ini dengan benar.

¹ Pertimbangkan misalnya fungsi . Jelas , tetapi tidak ada algoritma yang menghitung dalam waktu. $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$ $O(p(n)) = O(1)$ $p$ $O(1)$

complexity-theory sepp2k
sumber

1

Saya tidak berpikir dua pernyataan Anda dalam paragraf pertama Anda harus saling mendukung satu sama lain: bagaimana jika Anda memiliki sehingga ada beberapa masalah yang dapat diselesaikan di , bukan di , atau dalam waktu ?

f

$f$

O (f (n))

$O(f(n))$

o (f (n))

$o(f(n))$

Θ (f (n))

$\Theta(f(n))$

Alex ten Brink

@ Alex Itu poin bagus saya tidak mempertimbangkan itu.

sepp2k

13

Dengan teorema Gap (menggunakan formulasi dari sini , cari 'gap'), untuk setiap fungsi tak terbatas yang dapat dihitung , ada beberapa fungsi komputer yang dapat diperbesar (pada kenyataannya, semena-mena besar) sedemikian rupa sehingga . $g : \mathbb{N} \rightarrow \mathbb{N}$ $f : \mathbb{N} \rightarrow \mathbb{N}$ $DTIME(f(n)) = DTIME(g(f(n))$

Ini menjawab pertanyaan Anda bahwa terdapat ( sedemikian banyak, pada kenyataannya): untuk setiap fungsi yang dapat dihitung sedemikian sehingga , ada beberapa fungsi yang meningkat sehingga semua masalah dapat dipecahkan dalam waktu juga dapat dipecahkan dalam waktu . Perhatikan bahwa $f$ $g$ $g = o(n)$ $f$ $O(f(n))$ $O(g(f(n)) = o(f(n))$ $f$ belum tentu dapat dikonstruksi-waktu - untuk kasus yang dapat dikonstruksi-waktu, lihat jawabannya oleh @RanG.

Dalam formulasi Wikipedia (yang mensyaratkan bahwa ), maka menjadi Anda misalnya, dan kebutuhan untuk menjadi (sehingga Anda pergi sebaliknya - 'masalah dipecahkan di juga dapat dipecahkan dalam 'adalah bagian yang menarik). $g(x) \geq x$ $g \circ f$ $f$ $\omega(n)$ $O(g(f(n))$ $O(g(n))$

Artikel Wikipedia tidak mencatat bahwa meningkat dan sebenarnya bisa besar secara sembarang ( misalnya). Artikel yang membuktikan teorema gap memang menyebutkan dan membuktikan ini (lihat di sini , misalnya). $f$ $f(n) \geq g(n)$

Alex ten Brink
sumber

bisakah

menjadi

? Tidakkah diharuskan

? Pernyataan Anda masih benar, tetapi buktinya sebaliknya, bukan?

g

$g$

o (n)

$o(n)$

g (x) \geq x

$g(x)\ge x$

Ran G.

@RANG. Diperbarui untuk memberikan bukti untuk kedua formulasi (saya menggunakan formulasi di koran) :)

Alex ten Brink

"untuk setiap fungsi yang dapat dihitung g sedemikian sehingga g = o (n), ada beberapa fungsi f sehingga semua masalah yang dapat dipecahkan dalam waktu O (f (n)) juga dapat dipecahkan dalam O (g (f (n)) = o ( f (n)) waktu "Bagaimana jika semua fs yang ada untuk g berada di O (1)? Maka O (g (f (n)) masih O (1) dan dengan demikian bukan o (1).

sepp2k

@ sepp2k: tangkapan bagus, ini memang masalah yang dirumuskan. Saya telah memperbarui jawaban saya.

Alex ten Brink

12

Untuk setiap fungsi dihitung tidak terdapat masalah yang dapat diselesaikan di terbaik di waktu atau apakah ada fungsi komputasi sehingga setiap masalah yang dapat diselesaikan dalam bisa juga diselesaikan dalam waktu? $f$ $\Theta(f(n))$ $f$ $O(f(n))$ $o(f(n))$

Jika adalah fungsi yang dapat dikonstruksi waktu , maka Teorema Hierarki Waktu mengatakan bahwa ada masalah yang memerlukan waktu , dan tidak dapat diselesaikan dengan waktu $f$ $O(f(n))$ . Secara khusus, $o\left (\frac{f(n)}{\log(f(n))}\right )$

DTIME (Hai (\frac{f (n)}{catatan (f (n))})) ⊊ DTIME (f (n))

$\text{DTIME}\left ( o\left (\frac{f(n)}{\log(f(n))}\right) \right ) \subsetneq \text{DTIME} \left ( f(n) \right)$

Ini hanya mempertimbangkan masalah keputusan, dan tidak menganggap waktu yang dibutuhkan untuk menghasilkan output.

Ran G.
sumber

Apakah saya benar berasumsi bahwa jika kita mempertimbangkan fungsi-fungsi yang tidak dapat dikonstruksi waktu, jawaban atas pertanyaan saya adalah "tidak"? Atau terkait: jika suatu fungsi

tidak dapat dikonstruksi-waktu dan dengan demikian tidak ada mesin Turing yang berhenti setelah langkah

, apakah itu berarti juga tidak ada mesin Turing yang berhenti setelah langkah

? Karena dari situ akan dengan sepele mengikuti bahwa jawaban untuk pertanyaan saya adalah tidak.

f

$f$

f (n)

$f(n)$

Θ (f (n))

$\Theta(f(n))$

sepp2k

Tergantung. Asumsikan

tidak konstruktif waktu tetapi dapat dibatasi oleh beberapa fungsi lain

yang konstruktif waktu.

dan masih ada masalah yang dapat diselesaikan dengan waktu

tetapi tidak terlalu jauh dari itu.

f

$f$

g

$g$

f = Θ (g)

$f=\Theta(g)$

O (f)

$O(f)$

Ran G.

dan menggunakan beberapa TM tape, Anda dapat meningkatkan hasil dari

hingga

.

o (\frac{f (n)}{\lg f (n)})

$o(\frac{f(n)}{\lg f(n)})$

o (f (n))

$o(f(n))$

Kaveh

3

Saya akan mencoba memberikan sesuatu kerangka kerja dengan harapan memberikan wawasan yang lebih dalam.

Ketika Anda mendapatkan sesuatu yang mendasar ini ada jebakan yang tak terduga di mana-mana. Misalnya: apa artinya "memecahkan" masalah? Seringkali dalam ilmu komputer kita hanya mempertimbangkan varian "keputusan", di mana kita diberi input dan hanya perlu untuk menghasilkan Benar atau Salah. Anda berfokus pada masalah "fungsi".

Jika Anda menganggap notasi O (f (n)) sebagai upaya untuk menangkap berapa "kerja" yang diperlukan untuk menyelesaikan masalah, menggunakan keputusan alih-alih fungsi (di mana output diperlukan) tampaknya lebih baik karena Anda dengan bersih memisahkan perhitungan dari format output .

Saya tidak berpikir ini akan menjawab pertanyaan Anda, tetapi Anda mungkin tertarik pada ini: http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Juga, berhati-hatilah dengan teorema speedup .

agorenst
sumber

Untuk setiap fungsi yang dapat dihitung,

Jawaban: