Hottest Questions This Month

19

votes

5

answers

4k

views

What is the formal, rigorous definition of a programming language?

programming-languages

modified yesterday 6005 3,510

1

vote

7

answers

3k

views

Why can't we say that a Neural Network is a NP problem solver?

modified yesterday gnasher729 20.1k

5

votes

4

answers

1k

views

Is it possible for the runtime and input size in an algorithm to be inversely related?

algorithms complexity-theory time-complexity

modified Sep 8 at 7:27 Fabian 11

20

votes

2

answers

741

views

What is the intuition behind Strassen's Algorithm?

algorithms algorithm-analysis matrix-multiplication

modified Sep 13 at 9:24 Yuval Filmus 232k

13

votes

1

answer

1k

views

Are NP problems lower bounded by exponential order of growth?

complexity-theory

answered Sep 7 at 9:55 Yuval Filmus 232k

5

votes

2

answers

1k

views

What course in CS deals with the study of RAM, CPU, Storage?

cpu memory-allocation storage

answered Sep 13 at 21:05 ayasin 1

4

votes

1

answer

608

views

Is every unambiguous grammar regular?

formal-languages formal-grammars proof-techniques ambiguity

answered Sep 15 at 11:14 Yuval Filmus 232k

1

vote

3

answers

668

views

Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?

complexity-theory np-hard parameterized-complexity

modified Sep 6 at 6:09 a.t. 123

2

votes

2

answers

418

views

Definition of NP-hardness for non-decision problems

np-hard polynomial-time-reductions definitions

answered Aug 24 at 9:44 Tom van der Zanden 12.4k

-1

votes

3

answers

1k

views

Divide first n square numbers 1^2, 2^2, … n^2 into two groups such that absolute difference of the sum of the two groups is minimum [closed]

algorithms mathematical-programming

modified Sep 10 at 18:51 D.W.♦ 124k

4

votes

2

answers

244

views

Efficient Algorithm to Find the n-th Odious Number

algorithms number-theory counting

modified Sep 4 at 8:15 Yuval Filmus 232k

4

votes

2

answers

242

views

Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

combinatorics matrices

modified yesterday Peregring-lk 283

3

votes

1

answer

342

views

Why do we need a separate notation for П-types?

type-theory polymorphisms

modified Aug 25 at 10:43 hello world 175

3

votes

2

answers

108

views

Proof that L^2 is regular => L is regular

automata regular-languages

modified Aug 28 at 10:15 Idéophage 145

4

votes

1

answer

170

views

The same outgoing and incoming degree in graph

algorithms graphs network-flow

answered yesterday Yuval Filmus 232k

10

votes

1

answer

192

views

2-dimensional ranking of multiple arrays

algorithms

modified Sep 18 at 11:04 Albert Hendriks 2,094

4

votes

1

answer

179

views

Game on the graph with matchings

algorithms graphs matching

answered Sep 15 at 9:39 Yuval Filmus 232k

3

votes

1

answer

244

views

efficient algorithm for min cut with specified number of vertices

algorithms graphs time-complexity optimization

modified Aug 28 at 3:27 Dmitry 1,057

1

vote

2

answers

188

views

Automated reasoning with real numbers

constraint-satisfaction automated-theorem-proving smt-solvers

modified Aug 28 at 1:50 D.W.♦ 124k

6

votes

0

answers

500

views

What could we say about that conjecture that yields P != NP?

algorithms complexity-theory graphs computability np-complete

modified Sep 8 at 20:57 Dudi Frid 121

3

votes

1

answer

188

views

Does the term “continuity” have a different meaning in maths and in CS?

computability terminology

answered Aug 24 at 8:56 Arno 1,228

1

vote

2

answers

135

views

Time complexity of pairs in array double loop

time-complexity asymptotics big-o-notation

answered Sep 13 at 12:21 zkutch 171

5

votes

2

answers

130

views

Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?

algorithms dynamic-programming trees binary-trees recursion

modified Sep 7 at 8:24 maraca 101

2

votes

3

answers

98

views

Shortest path in modular arithmetic

number-theory modular-arithmetic

modified Sep 3 at 23:55 Ashwin Rajnish 11

1

vote

2

answers

121

views

NP-completeness of a Generalized Version of Subset Sum

np-complete reductions

modified Aug 30 at 1:30 Community♦ 1

3

votes

3

answers

151

views

What is the complexity of $i^i$?

time-complexity big-o-notation

modified Aug 27 at 10:51 Andrew Rashenda 31

1

vote

1

answer

51

views

For every imperative function, is there a functional counterpart with identical performance or even instructions?

compilers functional-programming haskell imperative-programming

modified Sep 13 at 22:46 Shreck Ye 145

0

votes

2

answers

54

views

Can we improve internet speed by serializing timestamps?

computer-networks

modified Sep 13 at 9:46 Jörg W Mittag 2,165

0

votes

3

answers

88

views

What are analog and digital in computer science?

turing-machines quantum-computing message-passing

modified Sep 4 at 11:39 George 3

3

votes

1

answer

80

views

Why Study Complexity Theory?

complexity-theory asymptotics

answered Sep 9 at 4:22 D.W.♦ 124k

1

vote

3

answers

61

views

Do the newest computers still have ROM?

computer-architecture

answered Aug 25 at 22:13 gnasher729 20.1k

2

votes

1

answer

70

views

Finding a boolean submatrix isomorphic to a specific fixed set of other boolean matrices

algorithms np-hard matrices

modified Sep 10 at 22:25 D.W.♦ 124k

3

votes

1

answer

87

views

Disprove unrealistic speed-up of total Turing machines

turing-machines time-complexity

modified Sep 1 at 11:25 Evil 9,065

4

votes

2

answers

132

views

Sequencing or continuation-passing in pure lambda-calculus

lambda-calculus

modified Sep 19 at 1:50 Dan Doel 1,376

0

votes

2

answers

79

views

How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

formal-languages regular-languages pumping-lemma

modified Sep 17 at 14:36 6005 3,510

3

votes

1

answer

99

views

+100

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

algorithms graphs colorings topological-ordering

modified 2 days ago Pål GD 8,556

1

vote

2

answers

97

views

Can $n = O(n^2)$?

algorithms asymptotics big-o-notation

answered Sep 13 at 1:26 zkutch 171

2

votes

3

answers

57

views

Determining the number of iterations needed to find the number of bits in an integer

time-complexity bit-manipulation

modified Sep 19 at 14:37 recursive 101

0

votes

2

answers

44

views

Are objects appropriate for modeling the real world?

simulation modelling object-oriented programming-paradigms philosophy

modified Sep 8 at 8:04 Aaron Rotenberg 3,267

3

votes

3

answers

92

views

Are there any examples of projects running a program that will take many years to finish its job?

time-complexity

answered Sep 1 at 6:01 Pseudonym 12.8k

2

votes

2

answers

71

views

Efficient way to count number of intersections of line segments

algorithms

modified Sep 1 at 18:43 John L. 23.8k

2

votes

1

answer

43

views

Does canonicity imply weak normalization?

type-theory

modified Sep 4 at 17:23 ice1000 774

3

votes

1

answer

52

views

Find a maximum matching that saturates a given set of vertices

graphs bipartite-matching

answered Sep 4 at 8:40 Erel Segal-Halevi 5,236

5

votes

0

answers

110

views

Impossibility of certain type of tree traversal algorithm

complexity-theory binary-trees

modified Sep 5 at 6:04 Yuval Filmus 232k

1

vote

2

answers

39

views

Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?

asymptotics landau-notation

answered Aug 25 at 16:24 Bernardo Subercaseaux 590

1

vote

1

answer

82

views

Reducing a problem to the MST problem

graphs minimum-spanning-tree

modified 20 hours ago Lorenzo Najt 355

1

vote

2

answers

70

views

Solving unusual recurrence with two variables

asymptotics recurrence-relation big-o-notation

answered Aug 26 at 13:18 gnasher729 20.1k

1

vote

2

answers

69

views

How to convert $(0.11001100…)_2$ to a decimal number

arithmetic boolean-algebra

answered Sep 15 at 14:56 Chris Custer 111

Top Questions

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.