Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

75

I'd say the most well known barriers to solving $P=NP$ are Relativization (as mentioned by Ran G.) Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs. Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize ...

57

Note: I haven't checked the answer carefully yet and there are missing parts to be written, consider it a first draft. This answer is meant mainly for people who are not researchers in complexity theory or related fields. If you are a complexity theorist and have read the answer please let me know if you notice any issue or have an idea about to improve the ...

54

There are a number of well-studied strategies; which is best in your application depends on circumstance. Improve worst case runtime Using problem-specific insight, you can often improve the naive algorithm. For instance, there are $O(c^n)$ algorithms for Vertex Cover with $c < 1.3$ ; this is a huge improvement over the naive $\Omega(2^n)$ and might ...

52

Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. For example, the function int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive: int g(...

34

Maybe the most common technique that cannot be used is relativization, that is, having a TM with oracle access. The impossibility follows from a paper by Theodore Baker, John Gill, Robert Solovay who show the existence of two oracles (languages), $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \ne \text{NP}^B$. Thus, if some proof for, ...

28

Here are three survey papers that examine the use of machine learning in time series forecasting: "An Empirical Comparison of Machine Learning Models for Time Series Forecasting" by Ahmed, Atiya, El Gayar, and El-shishiny provides an empirical comparison of several machine learning algorithms, including: "...multilayer perceptron, Bayesian neural ...

27

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity). By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid). By using Rings, we can do ...

25

In most type systems, the type rules work together to define judgements of the form: $$\Gamma\vdash e:\tau$$ This states that in context $\Gamma$ the expression $e$ has type $\tau$. $\Gamma$ is a mapping of the free variables of $e$ to their types. A type system will consist of a set of axioms and rules (a formal system of rules of inference, as Raphael ...

23

The term "true concurrency" arises in the theoretical study of concurrent and parallel computation. It is in contrast to interleaving concurrency. True concurrency is concurrency that cannot be reduced to interleaving. Concurrency is interleaved if at each step in the computation, only one atomic computing action (e.g. an exchange of messages between sender ...

23

No. That paper appears to be flawed. The flaw was explained in a comment by Tracy Hall on MathOverflow. A follow-up comment claims that the author later realized there is a flaw in his algorithm. As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed. When it comes to results on famous open ...

22

Roger Wattenhofer's Principles of Distributed Computing lecture collection is also a good place to start. It is freely available online, it assumes no prior knowledge on the area, and the material is very well up-to-date — it even covers some results that were presented at conferences a couple of months ago.

22

Positive result: persistence does not cost too much. One can show that every data structure can be made fully persistent with at most a $O(\lg n)$ slowdown. Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail). This incurs a $O(\lg n)$ slowdown: ...

21

Counting in the general case The problem you are interested in is known as #SAT, or model counting. In a sense, it is the classical #P-complete problem. Model counting is hard, even for $2$-SAT! Not surprisingly, the exact methods can only handle instances with around hundreds of variables. Approximate methods exist too, and they might be able to handle ...

20

Actually, until the 1950s the word computer was used to refer to a human who did arithmetic calculations. One (or more) of Richard Feynman's (many) autobiographies contains anecdotes about his time on the Manhattan project, where he ran the group of human computers. For arranging a group of humans to perform a complex computation they wouldn't start with ...

19

Vertex Cover has an algorithm running in time $1.2738^k + nk$, and is thus faster than $2^n n^2$, even with $k=n$. You can check out Table of FPT races for a short list of FPT running times of different problems. Here, $n$ is the number of vertices and $k$ is the solution size. Also, the question Are there subexponential-time algorithms for NP-complete ...

18

Classic, well-known results As mentioned by Standa Zivny on the related question of CSTheory, Which SAT problems are easy?, there's a well-known result by Schaefer from 1978 (quoting the answer of Zivny): If SAT is parametrised by a set of relations allowed in any instance, then there are only 6 tractable cases: 2-SAT (i.e. every clause is binary), Horn-...

18

The expressive completeness of the typed combinators compared to the simply typed lambda calculus has been demonstrated. For each untyped combinator, one needs a whole family of typed combinators. For example, one has $\mathbf{I}_{\alpha\to\alpha}$ $\mathbf{K}_{\alpha\to(\beta\to\alpha)}$ $\mathbf{S}_{\alpha\to(\beta\to\gamma)\to(\alpha\to\beta\to(\alpha\... 18 Historically, the term "strongly typed programming language" came into use in the 70's in reaction to the existing widely used programming languages, most of which had type holes. Some examples: In Fortran, there were things called "COMMON" storage areas, which could be shared across modules, but there were no checks to see if each module was declaring the ... 18 SMT solver is a SAT solver + decision procedure A SAT solver is a solver for a decision problem: the SAT problem is a decision problem. Additionally, this decision problem is "self-reducible": The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment ... 18 There is no "official Turing test" so there's no concept of "officially pass[ing] the test". Turing described a methodology that one might use to evaluate artificial intelligences. The organizers of the event that Eugene Goostman won implemented that methodology in a particular way and the program satisfied the criteria the organizers had chosen. In that ... 18 This is pretty much what TU Eindhoven's Computing Science education, designed and implemented by Dijkstra and colleagues, was like from the time it started, around 1980, until Dijkstra's influence started to wane, somewhere half way through the 1990s. I started studying CS at Nijmegen University in 1982; a classmate did the same at TU Eindhoven. Every ... 17 here is a half-baked answer: I know that Ugo Dal Lago at University of Bologna has been studying quantum lambda calculus. You may want to check his publications and perhaps this one in particular: Quantum implicit computational complexity by U. Dal Lago, A. Masini, M. Zorzi. I am saying it's a half-baked answer, because I haven't had chance to read any of ... 17 This is a good question. It appears that the term server was commonly used already in 1960s. For example, RFC 5, which was published in 1969, already uses the term, and it seems that it was in a common use already back then. However, the term client in this context seems to be much more recent; the earliest references that I was able to find are from 1978. ... 17 No, the graph isomorphism problem has not been solved. The paper you link to is from 2007–2008, and hasn't been accepted by the wider scientific community. (If it had been, I would have known about it.) Graph isomorphism, like many other famous problems, attracts many attempts by amateurs. They are almost always wrong. I would advise against trying to ... 17 Wikipedia says: An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm.$\mathcal{O}(\log n)$is upper bounded by$\mathcal{O}(n)$, and$\mathcal{O}(n \log n )$is upper bounded by$\mathcal{O}(n^2)$, therefore they are both in$P$. 16 As others have noted, books about (advanced) algorithms are best selected by topic. A good but heavy-weight general reference with rigorous analysis is probably The Art of Computer Programming by Knuth. As for analysis techniques, you may be interested in An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet, and Algorithmic Combinatorics ... 15 I think that learning about computer science certainly can be an advantage. Here are a number of (related) skills computer science has to offer. Programming – knowing how to program is a useful skill for any discipline. Statisticians and sociologists, geographers and engineers, and so on, often find themselves needing to program. Following a CS degree ... 15 Although many papers in theoretical computer science claims practical applications for their work, this is unfortunately often simply not the case. Usually, either the problems are too far away from being something useful (too simplified), or the algorithms are too far away from being practical (e.g. hiding big constants in the O-notation). However, you ... 15 Category theory is not necessary to understand programming languages, it's not even necessary to do advanced research on programming languages. Most programming language people don't know (much) category theory. Category theoretical methods have been useful mostly in a small part of programming language research, namely in the analysis of functional ... 15 Structural complexity theory studies the relation between different complexity classes, usually uniform ones. The two most famous open questions in the field are: Is$\mathsf{P} \neq \mathsf{NP}$? Is$\mathsf{P} = \mathsf{BPP}\$? In the past, a common pursuit in structural complexity theory was coming up with oracles that separate or join complexity ...

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