Questions tagged [intuition]
Questions that ask for help building intuition for formal or complex concepts.
11 questions
33
votes
7
answers
8k
views
Is there a more intuitive proof of the halting problem's undecidability than diagonalization?
I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization.
While the proof is convincing (I understand each step of ...
- 651
64
votes
8
answers
5k
views
Algorithmic intuition for logarithmic complexity
I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$.
In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
- 1,481
44
votes
2
answers
16k
views
Why do we believe that PSPACE ≠ EXPTIME?
I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME. If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, ...
- 443
28
votes
2
answers
11k
views
Rule of thumb to know if a problem could be NP-complete
This question was inspired by a comment on StackOverflow.
Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like ...
- 1,248
13
votes
3
answers
565
views
Why larger input sizes imply harder instances?
Below, assume we're working with an infinite-tape Turing machine.
When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I ...
user20
10
votes
3
answers
2k
views
Intuition for convolution in image processing
I have read many documents about convolution in image processing, and most of them say about its formula, some additional parameters. No one explains the intuition and real meaning behind doing ...
- 223
9
votes
5
answers
34k
views
How to tell if a language is recognizable, co-recognizable or decidable?
If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable?
Basically any hints or tricks that can be used to tell. Or maybe the ...
- 553
9
votes
4
answers
4k
views
Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?
I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists.
Is there a good / quick / easy way to see ...
- 1,117
2
votes
2
answers
1k
views
Why is automatically labeling data in unsupervised learning hard?
I currently studying machine learning and pattern recognition area. Today, my professor said implementing an unsupervised system that automatically labels data is difficult. Why is that?
I think if I ...
- 121
1
vote
5
answers
791
views
Google's Deep Dreamer
I was just wondering on a more technical side, if anyone could explain what Google does to create these amazing images from it's deep dream system.
Could anyone explain to me in a step by step way, ...
- 67
1
vote
2
answers
4k
views
How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?
I'm so bad at solving the problem of the type:
"If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ is..."
That I have to come here and ask these silly questions each and every time ...
- 859