[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 78 KB, 777x720, Complexity-classes-diagram.jpg [View same] [iqdb] [saucenao] [google]
11911194 No.11911194 [Reply] [Original]

what are the best books on computation?
looking to spend a few years to get a doctorate level understanding of the subject.

>> No.11911232
File: 29 KB, 332x499, 41cw1D0RWbL._SX330_BO1,204,203,200_.jpg [View same] [iqdb] [saucenao] [google]
11911232

>>11911194

>> No.11911241
File: 188 KB, 1280x720, 1ZGjEDn.jpg [View same] [iqdb] [saucenao] [google]
11911241

I recently started reading le meme computer book. It's good stuff if you're starting from the basics

>> No.11911248

>>11911194
What's the difference between exptime and expspace
t. a cs illiterate

>> No.11911717

>>11911194
The book suggested in >>11911232 is good for the basic theory. There's a lot of stuff from other subfields as well, but this book, Computers and Intractibility, and Oded's complexity book are all good starts.
>doctorate level
i mean, there's not really much you can do except get a doctorate. You can read the books but it's not the same as actually doing research

>> No.11912566

>>11911248
its in the name really

exptime algorithms are the one that take exponentially long depending on the size of input
expspace are algorithms whos inputs as they grow require exponential space on memory

>> No.11912569

>>11911194
One really has to wonder why cstards browse this board

>> No.11912572

>>11911194
its not really that hard really

get a good grasp on the basics of computation and a solid grasp on discrete math first and you're good to go

>> No.11913151

>>11911248
Every step of a Turing machine can read/write at most 1 thing on the tape during 1 step of computation. Algorithms which necessarily take exponential amounts of space to solve are then bounded on the bottom by taking exponentially many steps. However, we could easily devise algorithms that take double exponential time while only using exponential space, which is easy if you’ve seen any tricks with the unary language.
On the other hand, inclusion of EXPTIME in EXPSPACE is trivial - given exponential time, you can write at most exponential things to the tape.

>> No.11913161

>>11913151
that thing it writes is not a bit though, right? It can be some arbitrary symbol encoding any arbitrary amount of information?

>> No.11913206

>>11913151
This is a over complicated explanationthat is useless.

>>11913161
Exponential space complexity refers to the growth when creating space within memory to say solve a problem, the more space needed, the more time needed to create the space, think dynamic allocation of new memory continuously. Exponential would refer to the time being exponetial such that the big Onotation is O(2^n). As oppose to time complexity which refers to the time it takes for the the program to complete an algorithm, the iterations, the amount of overall text instructions in which the computer recieves in some way is all apart of the time complexity.

>> No.11913727

>>11913161
I mean, you can define a Turing machine with any arbitrary finite set of tape or input symbols. Either way, you can force them all to count exponentially far regardless of the tape alphabet by considering the unary language (the language of only 1 symbol), where the amount of symbols encodes the number.
>>11913206
>This is a over complicated explanationthat is useless.
this is literally an abbreviated explanation of the proof that EXPTIME is a subset of EXPSPACE but not equal. No step in this explanation is complicated.
> to say solve a problem, the more space needed, the more time needed to create the space, think dynamic allocation of new memory continuously. Exponential would refer to the time being exponetial such that the big Onotation is O(2^n).
And you think *my* explanation was contrived? Learn English lmao