Hottest Questions This Week

2

votes

3

answers

92

views

Is the P vs NP problem, an NP or co-NP problem?

complexity-theory p-vs-np

modified Aug 15 at 14:23 J. Schmidt 143

1

vote

2

answers

79

views

How do i tell if a grammar is regular or not?

modified Aug 15 at 15:01 rici 5,268

4

votes

1

answer

73

views

Intersection of O(n) expanding circles with line from the origin

algorithms computational-geometry

modified Aug 15 at 19:03 HEKTO 1,554

2

votes

2

answers

61

views

For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

graph-theory optimization graph-traversal weighted-graphs traveling-salesman

answered Aug 17 at 12:28 gnasher729 13.8k

1

vote

1

answer

82

views

+50

Merging nodes of a DAG

algorithms graphs graph-theory dag

modified 9 hours ago David 93

1

vote

2

answers

36

views

Big-O Notation and Calculus?

algorithms algorithm-analysis complexity-classes program-optimization big-o-notation

answered Aug 15 at 16:21 Juho 16.6k

0

votes

1

answer

46

views

Are every problems in EXP karp reducible to any EXP-Complete?

algorithms polynomial-time-reductions

modified 2 days ago Mohsen Ghorbani 175

2

votes

1

answer

45

views

HamiltonianCycles in Random Graphs

graphs hamiltonian-circuit

modified 1 hour ago New Seo 1

1

vote

1

answer

35

views

Are chatbots a good example of overfitting?

machine-learning artificial-intelligence

answered 2 days ago Derek Elkins 11k

1

vote

2

answers

34

views

Merge Sort Confusion - Initial Phase Missing?

mergesort

answered 2 days ago Curtis F 741

1

vote

1

answer

32

views

Solving/mitigating the free rider problem without requiring identification?

algorithms protocols

answered 2 days ago Derek Elkins 11k

4

votes

1

answer

47

views

Perfect Probabilistic Encryption still requires key length about as long as message

cryptography encryption

modified yesterday xskxzr 4,841

3

votes

1

answer

56

views

Problem in downvote system

algorithms computability combinatorics

answered Aug 15 at 8:29 ghellquist 281

0

votes

2

answers

33

views

What makes a common programming language non-context-sensitive but RE?

formal-languages context-sensitive

modified 8 hours ago dkaeae 4,255

1

vote

1

answer

23

views

What is the time complexity of a binary multiplication using Karatsuba Algorithm?

algorithms algorithm-analysis time-complexity arithmetic

modified Aug 13 at 20:53 Jakube 1,011

0

votes

1

answer

36

views

Verifying connectivity of a graph in O(n^2)

graphs graph-theory graph-traversal

modified Aug 16 at 12:18 Jack 1

0

votes

1

answer

35

views

What is a 'dynamic entity' in computer science?

operating-systems

modified yesterday HEKTO 1,554

1

vote

2

answers

34

views

Time complexity of finding predecessor for a dictionary implemented as a sorted array

algorithms algorithm-analysis time-complexity

modified Aug 17 at 15:46 rici 5,268

1

vote

1

answer

56

views

+50

TSP Variant — Colored Path

np-complete traveling-salesman

modified 14 hours ago Zachary Hunter 130

1

vote

2

answers

32

views

RSA cryptosystem: Encrypting a signed message

cryptography encryption

answered Aug 17 at 6:07 Navjot Waraich 770

1

vote

1

answer

23

views

What is the worst case time-complexity of removing the root of a Binary Search Tree?

time-complexity

modified 18 hours ago zaep 36

0

votes

1

answer

22

views

A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$

turing-machines computability reference-request

modified 7 hours ago dkaeae 4,255

0

votes

1

answer

36

views

“Greater than AND smaller than” condition in integer linear program with a binary variable

linear-programming integer-programming constraint-satisfaction

answered Aug 16 at 14:29 Dav 1

0

votes

0

answers

36

views

Algorithm for partitioning connected paths in an Array of 0s and 1s

algorithms

modified yesterday bitWise 1

0

votes

0

answers

35

views

What's the proof complexity of E-KRHyper (E-hyper tableau calculus)?

complexity-theory

asked Aug 15 at 20:30 Ricardo S. 54

-1

votes

1

answer

35

views

Conway game of life optimal state [closed]

cellular-automata

modified Aug 14 at 20:03 vonbrand 8,898

1

vote

1

answer

35

views

Write down a DFA for the regular expression (000* + 111) and explain why it cannot have lesser number of states

finite-automata regular-expressions

answered 22 hours ago Hendrik Jan 21.9k

1

vote

1

answer

27

views

Student Course Allocation Problem with Many Constraints [on hold]

algorithms graphs optimization network-flow bipartite-matching

answered Aug 14 at 14:54 vonbrand 8,898

2

votes

0

answers

34

views

Explain the process of formation of word senses in WordNet

natural-language-processing

asked Aug 13 at 18:59 Ricardo S. 54

0

votes

1

answer

25

views

Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s

formal-languages pushdown-automata

modified yesterday dkaeae 4,255

-3

votes

0

answers

30

views

What is the space complexity of the following procedure? [on hold]

algorithm-analysis space-complexity

modified 2 days ago NU LL 1

1

vote

1

answer

22

views

Is there a way to modify Kadane's Algorithm such that we know the resulting subarray?

algorithms maximum-subarray

answered Aug 14 at 11:01 Jakube 1,011

1

vote

1

answer

28

views

Why is it not always possible to compute the centroid of feature vectors?

data-mining features

modified Aug 14 at 20:55 Mads 6

-1

votes

0

answers

28

views

Is optimizing from O(n log n) to O(n) considered to be premature optimization? [on hold]

optimization asymptotics

modified Aug 17 at 14:54 太極者無極而生 122

-2

votes

0

answers

28

views

C programming : Stackoverflow is a cause of abrupt termination [on hold]

programming-languages

asked yesterday Ananya 1

-1

votes

0

answers

27

views

Linked List implementation with Priority Queue [on hold]

data-structures

asked Aug 16 at 12:37 Srestha1 1

0

votes

0

answers

27

views

Concatenative programming language based on the stack as a non-trivial virtual machine [on hold]

programming-languages compilers lambda-calculus stacks

modified Aug 16 at 13:34 Foxy 148

0

votes

0

answers

27

views

Modifying relaxation for the Bellman-Ford algorithm [on hold]

graphs graph-theory shortest-path weighted-graphs java

asked Aug 15 at 16:03 Jack 1

1

vote

2

answers

21

views

Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge?

proof-techniques

answered Aug 14 at 8:27 Yuval Filmus 206k

-2

votes

0

answers

25

views

What is the running time of the following procedure? [on hold]

algorithm-analysis time-complexity recursion

modified 2 days ago Jakube 1,011

2

votes

1

answer

19

views

How to prove an implication about an upper bound mentioned in the proof of master theorem?

algorithms

answered Aug 15 at 17:01 Yuval Filmus 206k

-3

votes

0

answers

24

views

Number of swaps and comparisons in sorting algorithms [on hold]

algorithms sorting

asked yesterday Debasis Panda 1

0

votes

0

answers

23

views

Conditions for string substitution commutativity

formal-languages substrings string-matching

modified Aug 16 at 8:36 alagris 1

0

votes

0

answers

22

views

Is there a language that pumps, but is not regular? [on hold]

regular-languages pumping-lemma

asked Aug 15 at 23:18 merhoo 11

-2

votes

0

answers

21

views

How to create a square root program without using math library in c++ [on hold]

algorithms c++

asked Aug 16 at 6:08 Mike Santosidad 1

0

votes

0

answers

21

views

Efficient method of representing bijections

discrete-mathematics permutations

asked 2 days ago RandomPerfectHashFunction 357

0

votes

1

answer

20

views

Getting erros on a Get&Set but don't understand why [on hold]

error-correcting-codes

answered Aug 15 at 21:04 gnasher729 13.8k

1

vote

1

answer

20

views

What is the meaning of uniform distribution of elements in an array?

algorithms data-structures search-algorithms arrays

answered Aug 15 at 19:59 Yuval Filmus 206k

Top Questions

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