Questions tagged [big-picture]

The big picture tag is for a "broad, overall view or perspective of an issue or problem."

Filter by
Sorted by
Tagged with
30
votes
7answers
9k views

Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ ...
24
votes
13answers
8k views

Complex analysis in theoretical computer science

There are many applications of real analysis in theoretical computer science, covering property testing, communication complexity, PAC learning, and many other fields of research. However, I can't ...
5
votes
2answers
2k views

Why were Finite Automata and Turing Machines created?

It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
247
votes
11answers
95k views

What is the enlightenment I'm supposed to attain after studying finite automata?

I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...
19
votes
4answers
9k views

Why is the consensus problem so important in distributed computing?

In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One ...
14
votes
1answer
614 views

Complexity class associated with exhaustive search

What is the complexity class associated with exhaustive search algorithms? (if there is one) Is it NP or PSPACE? Are there restricted models of computation capturing the class of exhaustive search ...
27
votes
5answers
2k views

Ecology and evolution through the algorithmic lens

The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very ...
2
votes
1answer
2k views

What are some good references for mathematical optimization for the layman?

I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' ...
9
votes
2answers
2k views

How/Why are linear systems so crucial to computer science?

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ...
14
votes
1answer
1k views

Speedup from algorithmic advances vs. hardware

I recall seeing a study or article a while ago claiming that most of the speedup seen in computer programs over the last several decades is from better algorithms rather than faster hardware. Does ...
7
votes
1answer
427 views

Papers on Prolog-like languages without closed world assumption (CWA)

Prolog execution process may be seen as a search that model scientific search for a proof of a proposition. At the same time, real world scientific search greatly differs from Prolog search in the ...
24
votes
2answers
2k views

Implications of proof of abc conjecture for cs theory

What implications would a proof of the abc conjecture have for tcs? http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
-10
votes
2answers
628 views

is every “nontrivial” algorithm Turing-complete?

recently there was a big response here to a question relating to the Church-Turing thesis.[1] this is another question that has nagged at me for close to a decade after studying some areas of TCS (...
14
votes
2answers
692 views

Landscape of interactive proof systems

My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively ...
4
votes
1answer
233 views

Surveys in other languages than English

Where can I find surveys in languages than English ? If the question is found to be interesting (it could be usefull for graduated students who are not fluent in English for instance), it would be ...
-6
votes
1answer
912 views

why is a Turing machine defined as a 5-tuple? [closed]

[Edited to provide better context.] In a comment on meta, JɛffE suggested that this would be a good topic for a question to ask here. why is a Turing machine defined as a 5-tuple?
8
votes
0answers
586 views

How hard is the origin of life problem?

The origin of life problem is the wide-ranging inquiry into the mechanisms underpinning the emergence of life, where one definition of life is "a self-sustained chemical system capable of undergoing ...
3
votes
2answers
237 views

Discerning the best model for a problem

This is a vague question. I will do my best, I think it has definite answers. I am hoping for answers of the form "Read book x, learn this specific topic, read this paper/s". What is bothering me is ...
6
votes
3answers
252 views

Asymmetry in Property Testing Definition

Property Testing refers to the problem of making a small number of queries to determine whether $x$ is in some language $L$ or whether it is far away from being in $L$. More precisely we want to ...
7
votes
0answers
330 views

Examples of non-CSLs not created through diagonalization

Hopcroft & Ullman 1979, Intro to Automata Theory, Languages, & Computation states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are ...
7
votes
1answer
378 views

Layman Interpretation: Quantum Factoring Algorithm

I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media. So, I'm hoping that somebody will be able to help me ...
12
votes
3answers
721 views

AM/MA and NP in analogy to P and BPP

Arora and Barak show that $\mathsf{AM}$ can be expressed as $\mathsf{BP}\cdot \mathsf{NP}$ i.e the set of languages that have randomized reductions to 3SAT. $\mathsf{MA}$ is also a natural randomized ...
67
votes
13answers
18k views

Uses of algebraic structures in theoretical computer science

I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (...
-6
votes
5answers
23k views

Application of calculus in computer science

Where are derivatives and integrals used in the field of Computer Science? What are their applications?
18
votes
11answers
4k views

Are there any applications of techniques in real analysis to theoretical computer science?

I have looked far and wide for such applications and have mostly turned up short. I can find plenty of applications of topology and similar structures on countable (or uncountable) sets, but rarely do ...
5
votes
2answers
375 views

(concise?) definition of thread safety

Wikipedia has the following definition: Thread safety is a computer programming concept applicable in the context of multi-threaded programs. A piece of code is thread-safe if it only ...
18
votes
4answers
2k views

Implications of unprovability of $P\neq NP$

I was reading "Is P Versus NP Formally Independent?" but I got puzzled. It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is not ...
2
votes
2answers
476 views

Are register based machines on von neumann architecture diametrically opposed to functional programming style?

We are so used to von neumann architecture and say a register machine like the x86. (Also with programming languages built for those machines x86 assembly, C, etc) Is that approach to computing ...
21
votes
5answers
2k views

Theoretical Applications for Approximation Algorithms

Lately I've started looking into approximation algorithms for NP-hard problems and I was wondering about the theoretical reasons for studying them. (The question is not meant to be inflammatory - I'm ...
25
votes
4answers
3k views

Arguments for existence of one-way functions

I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-...
17
votes
3answers
798 views

How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes

Teaser Since the problem is longish here is a special case that capture its essense. Problem: Let A be a detrministic algorithm for 3-SAT. Is the problem of completely simulating the algorithm A ...
38
votes
2answers
3k views

Mulmuley's GCT program

It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been ...
55
votes
4answers
22k views

Why is 2SAT in P?

I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
19
votes
1answer
615 views

Does cryptography have an inherent thermodynamic cost?

Reversible computing is a computational model that only allows thermodynamically reversible operations. According to Landauer's principle, which states that erasing a bit of information releases $kT ...
28
votes
17answers
2k views

Examples where insight from geometry was useful for solving something completely non-geometric

One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think ...
54
votes
3answers
2k views

Surprising algorithms for counting problems

There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples ...
32
votes
7answers
2k views

Algorithmic lens in the social sciences

Looking at questions through the algorithmic lens (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In ...
12
votes
4answers
711 views

What is the most important notion of sparsity for the design of efficient graph algorithms?

There are several competing notions of a "sparse graph". For instance, a surface-embeddable graph could be considered sparse. Or a graph with bounded edge density. Or a graph with high girth. A ...
7
votes
4answers
1k views

Approaching Number Theory conjectures through Graph Theory

i try to find if there was an attempt to prove any famous Number Theory conjectures like Goldbach conjecture or Twin Prime conjectures through Graph Theory. I have in my mind something like the ...
10
votes
3answers
1k views

Is there a theory to answer “the simplest program to solve a problem”?

To answer "what problems can be solved by computing", we developed the theory of computability. For the problems that are computable, is there a theory to answer the question "is the program I get the ...
10
votes
2answers
541 views

What happens if we improve the time hierarchy theorems?

In a nutshell, the time hierarchy theorems say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ ...
66
votes
7answers
4k views

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space....
61
votes
5answers
5k views

The origin of the notion of treewidth

My question today is (as usual) a bit silly; but I would request you to kindly consider it. I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
12
votes
2answers
656 views

Best alien communication protocol?

Let's say we discover alien civilizations that are able to send and receive messages using an interstellar digital communications channel. (Say using modulated radio waves, laser pulses, re-...
9
votes
3answers
471 views

Benefits for syntactic and semantic classes

This is a post separated from Consequences of UP equals NP, and also a follow-up question to Semantic vs. Syntactic Complexity Classes. In the above post we learned about the semantic and syntactic ...
6
votes
5answers
878 views

Why doesn't computer science follow biology more closely in computer design?

Nature has proved with the brain that it can create complex computers with very little energy consumed and released, extremely low energy compared to a common computer. However, I noticed the design ...
7
votes
3answers
506 views

How are proofs verified probabilistically in interactive proof systems?

I'm having a hard time understanding the way Arthur verifies proofs probabilistically with coin tosses in an intuitive manner. Suppose Arthur is a logician equipped with paper, a pencil and an ...
73
votes
5answers
3k views

Techniques for Reversing the Order of Quantifiers

It is well-known that in general, the order of universal and existential quantifiers cannot be reversed. In other words, for a general logical formula $\phi(\cdot,\cdot)$, $(\forall x)(\exists y) \...
13
votes
7answers
1k views

Mathematical analysis and computational complexity?

computational complexity involves large amounts of Combinatorics and number theory, some ingridiences from stochastics, and an emerging amount of algebra. However, being a analysist, I wonder whether ...
3
votes
3answers
1k views

Pseudo-polynomial time algorithms

Consider the following algorithm: Given a natural number as input, say $N$, the algorithm runs a loop (in which the algorithm does $O(1)$ time operations) $N$ times. Now, by definition of time ...