Mixing
What are some problems in P with high polynomial factors?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
What are some problems that are in P but the best known algorithm has a high polynomial factor ($ge 3$)?
time-complexity
asked 44 mins ago
Tomohiro Koana
1112
New contributor
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
2
down vote
favorite
What are some problems that are in P but the best known algorithm has a high polynomial factor ($ge 3$)?
time-complexity
asked 44 mins ago
Tomohiro Koana
1112
New contributor
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
What are some problems that are in P but the best known algorithm has a high polynomial factor ($ge 3$)?
time-complexity
asked 44 mins ago
Tomohiro Koana
1112
New contributor
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
What are some problems that are in P but the best known algorithm has a high polynomial factor ($ge 3$)?
time-complexity
time-complexity
asked 44 mins ago
Tomohiro Koana
1112
New contributor
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 44 mins ago
Tomohiro Koana
1112
New contributor
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 44 mins ago
Tomohiro Koana
1112
New contributor
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 44 mins ago
Tomohiro Koana
1112
asked 44 mins ago
Tomohiro Koana
1112
1112
New contributor
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Tomohiro Koana is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Concrete example: Thorup's $O(n^120)$ time algorithm to recognize half-squares of planar bipartite graphs.
https://arxiv.org/abs/1804.05793
Parameterized problem: Every parameterized $NP$-complete problem has arbitrarily large polynomial time algorithms. Like, finding $k$-clique of a graph can be solved by $O(n^k)$ algorithm. Computational geometry problems parameterized with the number of dimensions $d$ can be seen as a special case in this group.
answered 18 mins ago
Thinh D. Nguyen
1,5001241
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Concrete example: Thorup's $O(n^120)$ time algorithm to recognize half-squares of planar bipartite graphs.
https://arxiv.org/abs/1804.05793
Parameterized problem: Every parameterized $NP$-complete problem has arbitrarily large polynomial time algorithms. Like, finding $k$-clique of a graph can be solved by $O(n^k)$ algorithm. Computational geometry problems parameterized with the number of dimensions $d$ can be seen as a special case in this group.
answered 18 mins ago
Thinh D. Nguyen
1,5001241
add a comment |Â
up vote
2
down vote
Concrete example: Thorup's $O(n^120)$ time algorithm to recognize half-squares of planar bipartite graphs.
https://arxiv.org/abs/1804.05793
Parameterized problem: Every parameterized $NP$-complete problem has arbitrarily large polynomial time algorithms. Like, finding $k$-clique of a graph can be solved by $O(n^k)$ algorithm. Computational geometry problems parameterized with the number of dimensions $d$ can be seen as a special case in this group.
answered 18 mins ago
Thinh D. Nguyen
1,5001241
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Concrete example: Thorup's $O(n^120)$ time algorithm to recognize half-squares of planar bipartite graphs.
https://arxiv.org/abs/1804.05793
Parameterized problem: Every parameterized $NP$-complete problem has arbitrarily large polynomial time algorithms. Like, finding $k$-clique of a graph can be solved by $O(n^k)$ algorithm. Computational geometry problems parameterized with the number of dimensions $d$ can be seen as a special case in this group.
answered 18 mins ago
Thinh D. Nguyen
1,5001241
Concrete example: Thorup's $O(n^120)$ time algorithm to recognize half-squares of planar bipartite graphs.
https://arxiv.org/abs/1804.05793
Parameterized problem: Every parameterized $NP$-complete problem has arbitrarily large polynomial time algorithms. Like, finding $k$-clique of a graph can be solved by $O(n^k)$ algorithm. Computational geometry problems parameterized with the number of dimensions $d$ can be seen as a special case in this group.
answered 18 mins ago
Thinh D. Nguyen
1,5001241
answered 18 mins ago
Thinh D. Nguyen
1,5001241
answered 18 mins ago
Thinh D. Nguyen
1,5001241
answered 18 mins ago
Thinh D. Nguyen
1,5001241
1,5001241
add a comment |Â
add a comment |Â
Tomohiro Koana is a new contributor. Be nice, and check out our Code of Conduct.
Tomohiro Koana is a new contributor. Be nice, and check out our Code of Conduct.
Tomohiro Koana is a new contributor. Be nice, and check out our Code of Conduct.
Tomohiro Koana is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f97784%2fwhat-are-some-problems-in-p-with-high-polynomial-factors%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
