Scholar - Badge - Computer Science Stack Exchange

Scholar

Ask a question and accept an answer.

Awarded 11327 times.

is $IP=BPP^{NP}$

Awarded Apr 22 at 8:27

Soham Chatterjee

1236 bronze badges

How is there a paradox in the halting problem when you can trace it and it's very clearly non-halting?

Awarded Apr 21 at 6:42

Curious cat

32 bronze badges

How PDA decide when and which state to transform to?

Awarded Apr 21 at 4:43

Doerthous

1033 bronze badges

Can the optimization version of a problem be NP-hard while its decision version is in P?

Awarded Apr 20 at 18:57

joachimkristensen

133 bronze badges

Optimal worse-case sorting algorithm when some comparisons are cheap

Awarded Apr 20 at 16:17

zale

1134 bronze badges

I Don't Understand Nothing About Operating Systems even After reading books

Awarded Apr 19 at 15:34

gmmk

31 bronze badge

Measuring time complexity in the length of the input v/s in the magnitude of the input

Awarded Apr 18 at 21:27

Karan Mehta

1837 bronze badges

How can I find 2 median values of an array which is an union of 2 arrays in O(log n)?

Awarded Apr 16 at 20:42

111

33 bronze badges

Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$

Awarded Apr 14 at 19:00

Ank i zle

1536 bronze badges

Is the clique decision problem in co-NP?

Awarded Apr 12 at 0:33

Lilith

232 bronze badges

Is there a maximal set of programs that terminate?

Awarded Apr 11 at 12:08

timgo

1031 bronze badge

pumping lemma misunderstanding

Awarded Apr 9 at 17:26

user1701057

174 bronze badges

Reference request for book on design patterns with foreword by Christopher Alexander

Awarded Apr 8 at 17:03

Juan Meleiro

133 bronze badges

How to recover path, given unordered set of non-repeating arcs for directed graph?

Awarded Apr 7 at 3:31

IsalanOnkar

32 bronze badges

Multi-line fitting problem

Awarded Apr 5 at 10:22

codeR

538 bronze badges

Find orthogonal (integer) vectors in set

Awarded Apr 5 at 1:16

pommicket

2811 silver badge5 bronze badges

Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers

Awarded Apr 4 at 23:41

Ntwali B.

1613 bronze badges

Multiplication of subnormal and normal numbers under IEEE 754

Awarded Apr 4 at 1:11

pabloabur

132 bronze badges

Acyclic boolean circuit (DAG)

Awarded Apr 3 at 15:04

Emison Lu

133 bronze badges

Number of islands

Awarded Apr 3 at 12:57

SKPS

1033 bronze badges

What recurrence describes the time complexity of this algorithm?

Awarded Apr 1 at 22:21

Lucas Peres

1034 bronze badges

Designing a DFA with nth character condition for any integer n

Awarded Mar 31 at 14:31

NitayStack

153 bronze badges

Directed weighted multigraph with dynamic edges - shortest path

Awarded Mar 31 at 9:02

discrete coder

32 bronze badges

Distribute repeated values into bins as evenly as possible

Awarded Mar 30 at 20:17

DonQuiKong

1014 bronze badges

What can I read about permutations in 3D space?

Awarded Mar 28 at 19:49

BadCatss

1135 bronze badges

Time complexity to convert a truth table to a boolean circuit

Awarded Mar 27 at 16:36

Loic Stoic

1935 bronze badges

Select a subset of k intervals which form maximum length if we take union of these k intervals

Awarded Mar 24 at 20:22

Kitwradr

1235 bronze badges

Proving that there is no solution to the PCP problem using induction

Awarded Mar 24 at 18:25

Miszka

234 bronze badges

If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?

Awarded Mar 24 at 12:52

figsinwinter

235 bronze badges

Does a non-deterministic Turingmachine reach every possible result?

Awarded Mar 22 at 18:56

mathquester

32 bronze badges

Question about the length of certificate of an polynommial-time verifier

Awarded Mar 22 at 12:57

xxray

51 bronze badge

Is One Way TSP NP-Complete?

Awarded Mar 22 at 11:21

Darcy Sutton

32 bronze badges

Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?

Awarded Mar 22 at 7:42

Jerry Tao

234 bronze badges

What is the difference in heap configurations? Separation logic with CVC5 SMT solver

Awarded Mar 21 at 14:27

FrogOfJuly

1234 bronze badges

Checking forbidden moves in Renju

Awarded Mar 21 at 10:25

Kyaw Shin Thant

232 bronze badges

Is $n^n$ is a big-oh n factorial

Awarded Mar 20 at 20:34

taycants

32 bronze badges

Finding the Equation for Potential Method and Amortization Analysis

Awarded Mar 20 at 6:18

alienhunter

232 bronze badges

Find the asymptotic bound for the recurrence relation: $T(n) = T(\sqrt{n}) + 5n$

Awarded Mar 20 at 5:10

Yoxbox

32 bronze badges

How to determine agreement between two sentences?

Awarded Mar 18 at 15:12

Hamman Samuel

1314 bronze badges

Sorting array of strings (with repetitions) according to a given ordering

Awarded Mar 15 at 23:27

Pe Wu

1435 bronze badges

Minimum amount of parties containing round tables for everyone to meet each other

Awarded Mar 15 at 21:18

Tomyy

255 bronze badges

Strictness in both arguments but not in each individually

Awarded Mar 15 at 17:11

Marta

733 bronze badges

DFA that accepts strings whose 10th symbol from the right end is 1

Awarded Mar 15 at 7:05

steatoda

676 bronze badges

Determine bijective mapping using minimal number of lookups in subset mapping - standard problem / perspectives?

Awarded Mar 14 at 20:55

smheidrich

1134 bronze badges

Help with time complexity of a given code

Awarded Mar 14 at 18:56

complexity

32 bronze badges

How does a Turing machine read a transition table as a function?

Awarded Mar 14 at 18:40

Eris

132 bronze badges

Route planning on line segments which can be connected or not

Awarded Mar 14 at 13:34

GPrathap

1114 bronze badges

Is there a "Standard Algorithm" language, as used in academic papers?

Awarded Mar 14 at 13:26

Makketronix

3913 silver badges7 bronze badges

Subquadratic multiplication of polynomials in the max-plus/tropical semiring

Awarded Mar 14 at 12:26

ant_arctic

133 bronze badges

Algorithm/heuristic for large tournament matchup pairings

Awarded Mar 13 at 19:35

Ron M

1133 bronze badges

How do you calculate the amount of iterations the loop "for (i = 1; i < n^3; i += n)"

Awarded Mar 13 at 13:21

user19843013

12 bronze badges

What is a contracting grammar (in opposition to a non-contracting grammar)?

Awarded Mar 13 at 2:09

Vincent

2211 silver badge6 bronze badges

Can we prove the greedy algorithm archives 1.5-approximation for the Minimal Dominating Set Problem?

Awarded Mar 12 at 13:11

LostReminder

132 bronze badges

Shuffling two related sets together

Awarded Mar 11 at 18:16

Angstrom

1133 bronze badges

Compute the schedule which gives the maximum number of points

Awarded Mar 11 at 17:07

prcssngnr

1175 bronze badges

Transform a non-regular language into a regular one using sort

Awarded Mar 11 at 14:15

Anonymous

133 bronze badges

Can we transfer every DFA to DFAs with start state having no in edge?

Awarded Mar 11 at 12:50

Pouya Kafashi

352 bronze badges

How much does proving that a special case of a problem is NP-complete tell me about if the general problem is NP-complete?

Awarded Mar 10 at 22:49

Felix Jönsson

133 bronze badges

Is there an algorithm to test for an acyclic undirected graph, using edge data, not node data (e.g. adjacency matrix)

Awarded Mar 10 at 14:09

Ray Butterworth

2971 gold badge1 silver badge11 bronze badges

Why NP is not certain subset in P/poly?

Awarded Mar 10 at 9:47

Vladislav Ihost

1134 bronze badges

Prev 1

3 4 5

…

189 Next