25 votes

Theoretical Computer Science vs other Sciences?

As a theoretical computer scientist I am proud of the following achievements of the field. Logicians figured out that all logical connectives can be build from a single one, paving the road for ...
  • 27.5k
18 votes

Theoretical Computer Science vs other Sciences?

As a TCS researcher, I understand the feeling and feel it too sometimes. I think it is healthy to be able to appreciate the wonder that other sciences have to offer. We must also keep in mind that it ...
  • 8,223
11 votes

Theoretical Computer Science vs other Sciences?

I run a small software business producing XML processing tools, so I'm very much a practical engineer rather than a theoretician. It's 50 years since I did my CS degree. And you know, I'm constantly ...
9 votes

Theoretical Computer Science vs other Sciences?

My impression from your comments is that perhaps you have just not seen enough theoretical CS to get to some of the kind of content you are excited about in, say, physics. I'll also point out that you ...
4 votes

Theoretical Computer Science vs other Sciences?

Maybe I can offer some interesting point of view here: I finished my Bachelors degree in physics and started a bachelors degree in software engineering afterwards. People often ask me why, which the ...
3 votes

Sources that prove solving 2-SAT with DP takes linear time

It is a very basic exercise for undergraduate/graduate courses in Theoretical computer Science, and I think books avoid giving the solution so that students do not copy it without understanding. Here ...
  • 2,723
3 votes

Theoretical Computer Science vs other Sciences?

I recently saw a video of Richard Feynman (the famous physicist), in which he explains a bunch of physical phenomena. It’s on youtube, it‘s a famous one, and it completely blew my mind and it just got ...
  • 1,977
3 votes

Theoretical Computer Science vs other Sciences?

I have worked in IT for 27'ish years, and studied CS in Germany as well; even at a more theoretical uni (there was a separate "technical" uni in our city which got to do all the robotics ...
  • 219
2 votes

Theoretical Computer Science vs other Sciences?

Back in college, I loved TCS for the mental gymnastics. I'd argue that, for better or worse, they shaped the way my mind works: I'm a decent programmer and, generally, technologist and I think that's ...
1 vote

Theoretical Computer Science vs other Sciences?

It seems that your education has sparked (or noticeably deepened) your fascination for theory in general, a fascination you can experience and build upon in the field of TCS and could experience and ...
  • 193
1 vote

Theoretical Computer Science vs other Sciences?

There is a tension between theory and praxis in any discipline. In TCS, many ideas that are cooked up in labs as products of research and development eventually surface 20 years later in industry. ...
  • 111
1 vote

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

Thanks to Prof. @Yixin Cao's construction of the reduction, I think I have found a way to show that Planar-DFVS remains $\textsf{NP}$-hard when $(\Delta_{in}, \Delta_{out}) = (2, 2)$. We use the ...
  • 397
1 vote

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

Warning: this does not completely solve your question because the gadget is not planar. But since I could not find a proof of this, I think it might be worth posting. Speckenmeyer proved that the ...
  • 2,560
1 vote
Accepted

Short UNSAT Certificates for X3SAT

I can now prove my conjecture is false. The unsatisfiable 4 Pigeons in 3 Holes problem, when converted to linear, monotone X3SAT, does not have any completely blocked Conflict Clusters. A conflict ...
1 vote

Is the feedback vertex set problem on planar bounded degree graphs hard?

Here are the two gadgets Speckenmeyer used in his Ph.D. thesis. We can start from planar graphs with maximum degree six, by a reduction from the vertex cover problem on cubic planar graphs. (Actually, ...
  • 2,560

Only top scored, non community-wiki answers of a minimum length are eligible